Complexity Analysis
def permutations(arr, path=[]):
if not arr:
return [path]
result = []
for i in range(len(arr)):
result += permutations(
arr[:i] + arr[i+1:],
path + [arr[i]]
)
return resultWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n × n!)
Space
O(n × n!)
How to derive it
There are n! permutations, each of length n. Building each permutation involves n levels of recursion, and at each level we copy arrays (slicing is O(n)). Total: O(n × n!). The output stores n! permutations of length n → O(n × n!) space. The recursion tree has n! leaves and depth n.