1
$\begingroup$

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!)$?

$\endgroup$

1 Answer 1

-1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.