Why Time complexity of permutation function is O(n!)

People say this algorithm is O(n!) because there are n! permutations, but what you are counting here are (in a sense) function calls - And there are more function calls than n!:

• When str.length() == n, you do n calls;
• For each of these n calls with str.length() == n - 1, you do n - 1 calls;
• For each of these n * (n - 1) calls with str.length() == n - 2 you do n - 2 calls;
• ...

You do n!/k! calls with an input str of length k¹, and since the length goes from n to 0, the total number of calls is:

sum _{k = 0 ... n} (n!/k!) = n! sum _{k = 0 ... n} (1/k!)

But as you may know:

sum _{k = 0 ... +oo} 1/k! = e¹ = e

So basically, this sum is always less than the constant e (and greater than 1), so you can say that the number of calls is O(e.n!) which is O(n!).

Runtime complexity is often different from theoretical complexity. In theoretical complexity, people want to know the number of permutations because the algorithm is probably going to check each of these permutations (so there are effectively n! check done), but in reality there is much more thing going on.

_{¹ This formula will actually give you one compared to the values you got since you did account for the initial function call.}