CODEWITHSUNDEEP
pythontime-complexitybig-o
Badhreesh M Rao
Badhreesh M Rao

Reputation: 13

What is the Big O of this naive solution?

Here is a simple fucntion that takes in two input strings. It returns True if the second string is an anagram of the first.

def validAnagram(str1, str2):
    if len(str1) != len(str2):
        return False

    str1_arr = [char for char in str1]
    str2_arr = [char for char in str2]

    for char in str1_arr:
        if char in str2_arr:
            str2_arr.remove(char)
        else:
            return False
    return True

I am learning to calculate the Big O of the programs I write. Is this function's runtime O(N2) or O(N3)?

I assume its O(N3) because the "if" condition also runs O(N). So its 3 nested O(N) operations, resulting in O(N3) runtime. Please correct me if I am wrong.

Upvotes: 0

Views: 99

Answers (1)

Cihan
Cihan

Reputation: 2307

It is O(N^2). You have O(N) iterations, in which you perform an O(N) operation. This results in O(N^2) complexity overall.

I think what you got wrong is calculating this part to be O(N^2), while it's actually O(N):

    if char in str2_arr:
        str2_arr.remove(char)

because you have O(N) + O(N) here, which is still just O(N).

Upvotes: 1

Related Questions