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.