Can all permutations of a set or string be generated in O(n log n) time?

Problem Detail: 

I was looking over this question requesting an algorithm to generate all permutations of a given string. A comment in the answer caught my eye:

It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes only O(n log n) time for all permutations in total, so only O(1) -- constant time -- per permutation.

This seemed strange to me because the best method I was aware of to generate all permutations of a string is in O(2^n) time. Looking through the other results, I came across a response to a similar question which states: While it technically produces the desired output, you're solving something that could be O(n lg n) in O(n^n)

I am aware of an algorithm to unrank permutations in O(n log n) time, but these responses seem to imply that all permutations in total can be generated in time O(n log n). Am I misunderstanding these responses?

Asked By : Sam Vernalis

Answered By : Aryabhata

You have misinterpreted the SO question itself (or we have misinterpreted yours, which seems more likely). That SO quesiton is talking about generating a 'next' permutation from a previous given one, so that all permutations can be generated by calling 'next' multiple times.

The answer to that is talking about the (amortized) time complexity of the C++ implementation std::next_permutation which I believe uses Narayana Pandita's algorithm, and generates them in lexicographic order.

(Also, as an aside: permutations are different from combinations. There are $n!$ permutations, but $2^n$ combinations (subsets). You seem to be under the impression that permutation is same as a combination (based on your claim of $O(2^n)$)).

To get back to the original question, another way to look at the question: would using next_permutation to generate all the $n!$ permutations in lexicographic order be $\Theta(n!)$ or $\Theta(n\times n!)$?

While there are some wrong statements in the answer you linked, it does state the right answer: It is $\Theta(n!)$, i.e. the amortized time complexity of next_permutation is indeed $O(1)$.

This can be proven as follows:

If $T(n)$ is the time taken to generate all the $n!$ permutations using next_permutation then we have that

$$T(n) = n T(n-1) + O(n^2)$$

(You fix the first number $n$ times and generate the permutations for the rest, and pay $O(n)$ cost when the first number is switched.)

Let $G(n) = \dfrac{T(n)}{n!}$. Note that we are looking the the asymptotics of $G(n)$. We get

$$G(n) \le G(n-1) + \frac{cn^2}{n!}$$

This is a simple telescoping sum, and since $\sum_{n=1}^{\infty} \frac{n^2}{n!}$ is convergent, we get that

$$G(n) = O(1)$$

Note that you could have changed the recursion to

$$T(n) = nT(n-1) + O(n^k)$$

and still have gotten $O(1)$ amortized per permutation.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11611