What is the time complexity of generating all permutations of a list in Python? The following code is what needs to have its time complexity computed. How do I do this?
def permute(list):
tot_list = []
if len(list) == 1:
return [list]
for permutation in permute(list[1:]):
for i in range(len(list)):
tot_list.append(permutation[:i] + list[0:1] + permutation[i:])
return tot_list
The main challenge with analyzing this function is that there aren't that many recursive calls, but each call returns a progressively larger and larger list of elements. In particular, note that there are n! permutations of a list of n elements. Therefore, we know that if you make a recursive call on a list of size n, there will be n! elements returned.
So let's see how this is going to influence the runtime. If you have a list of just one element, the time complexity is O(1). Otherwise, let's suppose that you have n + 1 elements in the list. The algorithm then
We can analyze the total runtime for the recursion by just looking at the work done at each level of the recursion, meaning that we'll focus on steps (2) and (3) right now.
Notice that in step 2, if there are n + 1 elements in the list, we will have to look at n! permutations generated by the recursive call. Each of those permutations have n elements in them. For each permutation, we make n + 1 new lists, each of which has n + 1 elements in it. Therefore, we have n! loop iterations, each of which does (n + 1)2 work. Consequently, the total work done at this level is (roughly) (n + 1)2 · n!. We can note that (n + 1) · n! = (n + 1)!, so the work done could be written as (n + 1)(n + 1)!. This is strictly less than (n + 2)!, so we could say that the work done when there are n + 1 total elements is O((n + 2)!). (Note that we can't say that this is O(n!), because n! = o((n + 2)!)).
So now we can say that the total work done is (roughly speaking) given by
1! + 2! + 3! + ... + (n + 1)!
To the best of my knowledge, this doesn't have a nice, closed-form formula. However, we can note that
1! + 2! + 3! + ... + (n + 1)!
< (n + 1)! + (n + 1)! + ... + (n + 1)!
= (n + 2)(n + 1)!
= (n + 2)!
So the overall expression is O((n + 2)!). Similarly, we have that
1! + 2! + 3! + ... + (n + 1)!
> (n + 1)!
So the overall expression is Ω((n + 1)!). In other words, the true answer is sandwiched (asymptotically) somewhere between (n + 1)! and (n + 2)!. Therefore, the runtime grows factorially fast.
Hope this helps!
