## Time Complexity of permutation function

Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] My Iterative Solution is : public List> permute(int[] nums) { List

> result = new ArrayList<>(); result.add(new ArrayList<>()); for(int i=0;i

> temp = new ArrayList<>(); for(List a: result) { for(int j=0; j<=a.size();j++) { a.add(j,nums[i]); List current = new ArrayList<>(a); temp.add(current); a.remove(j); } } result = new ArrayList<>(temp); } return result; } My Recursive Solution is: public List > permuteRec(int[] nums) { List

> result = new ArrayList

>(); if (nums == null || nums.length == 0) { return result; } makePermutations(nums, result, 0); return result; } void makePermutations(int[] nums, List

> result, int start) { if (start >= nums.length) { List

temp = convertArrayToList(nums); result.add(temp); } for (int i = start; i < nums.length; i++) { swap(nums, start, i); makePermutations(nums, result, start + 1); swap(nums, start, i); } } private ArrayList convertArrayToList(int[] num) { ArrayList item = new ArrayList (); for (int h = 0; h < num.length; h++) { item.add(num[h]); } return item; } According to me the time complexity(big-Oh) of my iterative solution is: n * n(n+1)/2~ O(n^3) I am not able to figure out the time complexity of my recursive solution. Can anyone explain complexity of both?

## Solutions/Answers:

### Answer 1:

The recursive solution has a complexity of `O(n!)`

as it is governed by the equation: `T(n) = n * T(n-1) + O(1)`

.

The iterative solution has three nested loops and hence has a complexity of `O(n^3)`

.

However, the iterative solution will not produce correct permutations for any number apart from `3`

.

For `n = 3`

, you can see that `n * (n - 1) * (n-2) = n!`

. The LHS is `O(n^3)`

(or rather `O(n^n)`

since `n=3`

here) and the RHS is `O(n!)`

.

For larger values of the size of the list, say `n`

, you could have `n`

nested loops and that will provide valid permutations. The complexity in that case will be `O(n^n)`

, and that is much larger than `O(n!)`

, or rather, `n! < n^n`

. There is a rather nice relation called Stirling's approximation which explains this relation.

### Answer 2:

It's the *output* (which is huge) matters in this problem, not the routine's implementation. For `n`

distinct items, there are `n!`

permutations to be returned as the answer, and thus we have at least `O(n!)`

complexity.

With a help of Stirling's approximation

```
O(n!) = O(n^(1/2+n)/exp(n)) = O(sqrt(n) * (n/e)^n)
```

we can easily see, that `O(n!) > O(n^c)`

for *any* constant `c`

, that's why it doesn't matter if the implementation itself adds another `O(n^3)`

since

```
O(n!) + O(n^3) = O(n!)
```

## References

- Database Administration Tutorials
- Programming Tutorials & IT News
- Linux & DevOps World
- Entertainment & General News
- Games & eSport