CODEWITHSUNDEEP
pythonalgorithmtime-complexitybacktracking
Mx321
Mx321

Reputation: 31

What would be the time complexity of this backtracking algorithm for finding permutations?

I am trying to determine the time and space complexity of this algorithm I created to find all permutations of an array in Python. Is the time complexity O(sum_{k=1}^N P(n,k)) where P(n,k) is a permutation with k factors?

class Solution:
    def permute(self, vals):
        answer = [vals]
        def backtrack(i, curr_arr):
            if i >= len(vals):
                return
            curr_val = curr_arr[i]
            for j in range(i + 1, len(vals)):
                permutation = curr_arr.copy()
                temp_val = curr_arr[j]
                permutation[j] = curr_val
                permutation[i] = temp_val
                answer.append(permutation)
                backtrack(i + 1, permutation)
            backtrack(i + 1, curr_arr)
        backtrack(0, vals)
        return answer

Upvotes: 1

Views: 359

Answers (1)

trincot
trincot

Reputation: 350365

If the given input has size 𝑛, then there are n! permutations for it. This means that append will be executed 𝑛!−1 number of times (excluding the initialisation with = [vals]). So curr_arr.copy() is executed as many times. As a single execution of it has O(𝑛) time complexity, the time complexity for executing them all is O(𝑛.𝑛!). All other instructions have (amortised) constant time complexity, so this represents the overall time complexity.

For the space complexity we must count the depth of the recursion, which is O(𝑛). We should also count the memory for the answer, which is the size of one permutation times the number of permutations, so O(𝑛.𝑛!). The space used for recursion is therefore negligible compared to that.

Conclusion: both time and space complexity are O(𝑛.𝑛!)

Upvotes: 2

Related Questions