Big-O analysis of permutation algorithm

Question

result = False
def permute(a,l,r,b):
    global result
    if l==r:
        if a==b:
            result = True
    else:
        for i in range(l, r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r, b)
            a[l], a[i] = a[i], a[l]

string1 = list("abc")
string2 = list("ggg")
permute(string1, 0, len(string1)-1, string2)

So basically I think that finding each permutation takes n^2 steps (times some constant) and to find all permutations should take n! steps. So does this make it O(n^2 * n!) ? and if so does the n! take over, making it just O(n!)?

Thanks

edit: this algorithm might seem weird for just finding permutations, and that is because i'm also using it to test for anagrams between the two strings. I just haven't renamed the method yet sorry

Answer 1

Finding each permutation doesn't take O(N^2). Creating each permutation happens in O(1) time. While it is tempting to say that this O(N) because you assign a new element to each index N times per permutation, each permutation shares assignments with other permutations.

When we do:

a[l], a[i] = a[i], a[l]
permute(a, l+1, r, b)

All subsequent recursive calls of permute down the line have this assignment already in place.

In reality, assignments only happen each time permute is called, which is times. We can then determine the time complexity to build each permutation using some limit calculus. We take the number of assignments over the total number of permutations as N approaches infinity.

We have:

Expanding the sigma:

The limit of the sum is the sum of the limits:

At this point we evaluate our limits and all of the terms except the first collapse to zero. Since our result is a constant, we get that our complexity per permutation is O(1).

However, we're forgetting about this part:

if l==r:
    if a==b:
        result = True

The comparison of a == b (between two lists) occurs in O(N). Building each permutation takes O(1), but our comparison at the end, which occurs for each permutation, actually takes O(N). This gives us a time complexity of O(N) per permutation.

This gives you N! permutations times O(N) for each permutation giving you a total time complexity of O(N!) * O(N) = O(N * N!).

Your final time complexity doesn't reduce to O(N!), since O(N * N!) is still an order of magnitude greater than O(N!), and only constant terms get dropped (same reason why O(NlogN) != O(N)).