## 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<>();
for(int i=0;i> temp = new ArrayList<>();
for(List a: result)
{
for(int j=0; j<=a.size();j++)
{
List current = new ArrayList<>(a);
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);
}
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++) {
}
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?
```

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.

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!)
``````