# Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums.

    def permute(nums):
res = []
dfs(nums, [], res)
return res

def dfs(nums, curr, res):
if not nums:
res.append(curr)
return
for i in range(len(nums)):
dfs(nums[:i]+nums[i+1:], curr+[nums[i]], res)


I think that the run time on an input of size $$n$$ is $$T(n)=nT(n-1)+n$$ because the function will make $$n$$ recursive calls on an input of size $$n-1$$ and it loops over $$n$$ terms. This gives $$T(n)\in \mathcal O(n!)$$ but some people say that it is $$\mathcal O(n\cdot n!)$$. Is the runtime of this $$\mathcal O(n!)$$ or $$\mathcal O(n\cdot n!)$$?

Consider this piece of code:

        for i in range(len(nums)):
dfs(nums[:i]+nums[i+1:], curr+[nums[i]], res)


Note that curr+[nums[i]] creates a new list, and on the bottom level, each of the $$n!$$ new lists will have size $$n$$. Hence $$\mathcal{O} (n! \cdot n)$$ total complexity.

On the other side, note that the complexity nums[:i]+nums[i+1:] is also linear in terms of $$n$$, but it does not present a problem, since its length at the bottom levels is $$\mathcal{O} (1)$$.

To look at it another way, the output has a size of $$n! \cdot n$$, so, barring any clever tricks in storing the output, the whole algorithm can't take less than that to produce the whole output.

In terms of recurrence relation, it gets a bit tricky, as the deeper we go, the larger the second argument (curr) gets. So, perhaps we can write $$T (n, \ell) = n \cdot T (n - 1, \ell + 1) + n \cdot (n + \ell)$$, where $$n$$ is the length of nums, and $$\ell$$ is the length of curr. We are interested in $$T (n, 0)$$, and the base is $$T (0, \ell) = \ell$$.