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

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?

## 1 Answer

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.

• 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? – dir101 May 12 '20 at 20:22