What is the time and space complexity of this solution?

Question

Python

Solved the problem on List Permutation:
That is, for [1,2,3], the permutations are
['1', '2', '3']
['1', '3', '2']
['2', '1', '3']
['2', '3', '1']
['3', '1', '2']
['3', '2', '1']

My solution:

def getPermutations(array):
  if len(array) == 0:
    return []
  elif len(array) == 1:
    return [array]
    
  last_elem = array[-1:]
  all_elem_except_last = array[:-1]
  
  permutations = getPermutations(all_elem_except_last)
  
  new_permutations = []
  
  for permutation in permutations:
    for i in range(len(permutation)+1):
      new_permutation = permutation[:i] + last_elem + permutation[i:]
      new_permutations.append(new_permutation)
      
  return new_permutations

Answer 1

Let's make a recurrence relation. Let F(n) be how long your function runs when it enters n elements.
In the function:
- A new array is allocated: n operations
- A function is called for a shortened array: F(n-1) operations
- Loop through all permutations of n-1 elements: (n-1)! repetitions
- Nested loop over positions: n*(n-1)! =n! repetitions
- construction of a new permutation nested in cycles: n * n! operations
Total F(n) = n + F(n-1) +n*n!
We can expand it recursively and get:
F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
Carefully looking at this, you can understand that all terms, starting from (n-1)*(n-1)!, are less than n*n! in total, and the first n terms are generally scanty and can be discarded.
As a result, F(n) = O(n*n!).
Please note that it is not enough just to take the biggest member. There are n of them, and if they were of approximately the same order, then another factor n would appear in the answer. But here the rest of the terms are at least n times smaller than the largest one.
The memory complexity is the same - after all, you end up storing all the permutations there, there are n of them! and each occupies n. But this is an estimate of the asymptotics - O(n*n!). In fact, there will be a little more than n * n! elements, because it stores a list of the answer and a list for smaller permutations, plus a stack and intermediate arrays when concatenating.
This is a good asymptotics - less can be done to construct all permutations.
However, if you do not need to store all permutations in memory (and for the cache, by the way), it will be noticeably faster to generate the next permutation from the current one in place, as described here . Although with the same asymptotics, this algorithm will work several times faster.