Time Complexity of permutation function

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

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.