CODEWITHSUNDEEP
pythonpython-3.xalgorithmruntimebig-o
Jeff
Jeff

Reputation: 170

What is big O notation of these permutation algorithms

Working my way through "Cracking the coding interview", and a practice question says

Given 2 strings, write a method to decide if one is a permutation of the other.

The author's python solution is as follows:

def check_permutation(str1, str2):
    if len(str1) != len(str2):
        return False
    counter = Counter()
    for c in str1:
        counter[c] += 1
    for c in str2:
        if counter[c] == 0:
            return False
        counter[c] -= 1
    return True

Which claims to be in O(N) time.

My solution is as follows:

def perm(str1,str2):
    if(len(str1) != len(str2)):
        return False
    for c in str1:
        if c not in Str2:
            return False
    return True

And I believe this to also be O(N). Is this true? Which algorithm is favorable? The author's data type seems unneccesary.

And lastly, is this algorithm O(NlogN)?

def perm(str1,str2):
    return sorted(str1)==sorted(str2)

Upvotes: 1

Views: 229

Answers (2)

OmG
OmG

Reputation: 18838

For the first code, it could be easy by using collection.Counter instead of loops:

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

And it is O(n) again. The last algorihtm, as there is a sorting and using sorted it is O(nlogn).

Your algorithm is not true as you find a character inside the other string without concern of the number of the repetition of that character. If it was true, it would be O(n^2).

Therefore, in a general sence, the first algorithm has the best time complexity and easy to be implemented.

Upvotes: 0

sds
sds

Reputation: 60014

First, the author's solution is an optimized version of Counter(str1) == Counter(str2) (it returns False faster and creates a single instance of a Counter). It is, indeed, O(n) because hash table (Counter) access is O(1).

Next, your solution is quadratic (O(n^2)) because each in is O(n) - it has to traverse the whole string. It is also wrong on strings with repetitions.

Third, sorted(str1) == sorted(str2) is, indeed, linearithmic (O(n*log(n))) and thus is worse than the original linear solution.

Note, however, that for small strings the constants may make a difference and the linearithmic (sorted) solution may turn out to be faster than the linear (Counter) one.

Finally, beware that Python is usually implemented using an interpreter, so the actual performance may depend on whether you are using features implemented in C or in Python. E.g., if Counter is implemented in C, then Counter(str1) == Counter(str2) will probably outperform the author's solution hands down, even though algorithmically the author's solution is better.

Upvotes: 3

Related Questions