Time and Space Complexity of Leetcode Problem #31. Next Permutation

Question

The question is as follows: Given a collection of distinct integers, return all possible permutations. Example:

Input: [1,2,3]
Output:
[
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
]

Here is my backtracking solution for the problem, where I added the num_calls variable to keep track of the number of times that the backtrack function is called recursively.

class Solution:
 def permute(self, nums):
 answer = []
 num_calls = []
 def backtrack(combo, rem):
 if len(rem) == 0:
 answer.append(combo)
 for i in range(len(rem)):
 num_calls.append(1)
 backtrack(combo + [rem[i]], rem[:i] + rem[i + 1:])
 if len(nums) == 0:
 return None
 backtrack([], nums)
 print(len(num_calls))
 return answer

I can't make sense of any of the answers that I have seen thus far for the time and space complexity of this solution.

Some people say its worst case O(n * n!), but looking at the len of num_calls doesn't verify this claim.

For example, for:

test = Solution()
print(test.permute([1, 2, 3]))

length of num_calls = 15, which != n * n! = 3 * (3*2*1) = 18

, for:

test = Solution()
print(test.permute([1, 2, 3, 4]))

length of num_calls = 64, which != n * n! = 4 * (4*3*2*1) = 96.

, and for:

test = Solution()
print(test.permute([1, 2, 3, 4, 5]))

length of num_calls = 325, which != n * n! = 5 * (5*4*3*2*1) = 600

Can someone please explain this in a simplified and easily understandable manner?

Answer 1

The number of calls indeed grows slower than \$n*n!\$. Its growth is only \$O(n!)\$. However, number of calls is not the only source of complexity.

Constructing arguments for the recursive call also takes time, and rem[:i] + rem[i + 1:] is on average linear in terms of n. The total complexity therefore is \$O(n*n!)\$, just as some people say.

• ny_coder_dude: How is the growth of the number of calls only O(n!)? For each of the examples I showed above, the number of calls is greater than n!. In addition, could you explain a bit more as to why rem[:i] + rem[i + 1:] is on average linear?