What is the complexity of this algorithm and is there a possibility to improve it?

This is the algorithm of this problem: Write a function that takes two arrays as input, each array contains a list of A-Z; your program should return True if the 2nd array is a subset of 1st array, or False if not.

# Python 3 program to find whether an array

def isSubset(arr1, arr2):
    i = 0
    for i in range(len(arr2)):
        if(arr2[i] not in arr1):
            return False
    return True
     
arr1 = ["A", "B", "C", "D", "E", "F"]
arr2 = ["C", "A", "A"]

if(isSubset(arr1, arr2)):
    print("arr2[] is a subset of arr1[] ")
else:
    print("arr2[] is not a subset of arr1[]")

Answer

The complexity of your algorithm is O(n*k), where n and k is length of arrays. You have one loop inside another one and search in the list takes O(n)

for i in range(len(arr2)):
     if(arr2[i] not in arr1)  # inner loop because of `in` with `O(n)` complexity

You can optimize your algorithm:

s = set()
for el in arr1:
  s.add(el)

for el in arr2:
  if el not in s:
     return False

return True

In this case the time complexity is O(n+k), where n and k is length of arrays. Search in the set (and dict has O(1) time complexity).

But is this case you need an additional space for set. So new algorithm has O(n) space complexity while original one – O(1).