
The next_permutation works like this:
it looks for a longest decreasing sequence in the end ant then does a swap and reverse.
For example, if the current permutation ends in 2,4,3,1 then the longest decreasing sequence is 4,3,1. It swaps 2 and the smallest element that is bigger than it, in our case it's 3. So we have 3,4,2,1. And then reverse the last (still decreasing) sequence, so we have 3, 1, 2, 3. In other words for each decreasing sequence of length K it does O(K) operations.
How many permutations with the longest decreasing sequence in the end with length 1? It's n!/2. With length 2? It's n!/6 and so on...
So, we have a sum n! * ( 1/2! + 2/3! + ... + (n1)/n! ) which is easily evaluated to n! * (1  1/n!), which is O(n!). 