1. Is an array a subset of another array?

Shorter array: arr_s
Longer array: arr_l

2. Array Solution: Nested-Loops - \(O(N*M)\)

# arr_s = [char for char in "bdf"]
arr_s = [char for char in "bdfz"]
arr_l = [char for char in "abcdef"]

for chr_s in arr_s: # O(N)
    match_found = False
    for chr_l in arr_l: #O(M)
        # print(chr_s,chr_l)
        if chr_s==chr_l: 
            match_found = True   
            break
    chr_s_not_found = chr_s # Total O(N*M)
    
if match_found:
    print(f"Subset: {match_found}")
else:
    print(f"Subset: {match_found}. Character not found: {chr_s_not_found}")

Subset: False. Character not found: z

3. Time-Complexity with a Hash Table - \(O(N)\)

By implementing a hash-table (python dict), the time-complexity of our algorithm improves significantly:

Reduced from \(O(N*M)\ \to\ O(N)\)

# arr_s = [char for char in "bdf"]
arr_s = [char for char in "bdfz"]
arr_l = [char for char in "abcdef"]

# create dict_l -> dctkeys= char_l of arr_l, dctvals = True
dict_l = {}
for char_l in arr_l: # O(N)
    dict_l[char_l]=True
    
# print(dict_l)

# check char_s in dict_l
for char_s in arr_s: # O(N)
    match_found = False
    if char_s in dict_l: # O(1) 
        match_found = True
    char_s_not_in_dict_l = char_s # Total O(N+N+1) = O(2N+1) = O(N)

if match_found:
    print(f"Subset: {match_found}")
else:
    print(f"Subset: {match_found}, Character not found: {char_s_not_in_dict_l}")

Subset: False, Character not found: z