Heap's algorithm time complexity

Question

can anyone tell me what exactly is the time complexity of this Heap's algorithm shown in wikipedia, https://en.wikipedia.org/wiki/Heap%27s_algorithm ?

I searched several websites and the answers are all vague, some of them say the time complexity is O(N!) some of them say it's O(NlogN). Which one is the correct answer? And why?

Thank you.

Muncy

Answer 1

There are N! permutations in all and generating all of them requires Θ(N!) time and Θ(N) space. In other words, each permutation requires amortised Θ(1) time.

Those facts can be derived from the recursive algorithm presented on the Wikipedia page. In essence, the code alternates swaps and outputs so each output involves a single swap.

However, there are also call operations and loop tests. There is a single loop test before each call, so it is only necessary to count the total number of calls.

In the worst case, there will be n recursive calls before an output. But that only happens once, at the very beginning of the algorithm. A single call with argument n produces n! outputs. It does that with n recursive calls, each of which produces (n-1)! outputs, and does (n-1) recursive calls, so there are n(n-1) calls with argument n-2. And so on, so there are a total of 1 + n + n(n-1) + n(n-1)(n-2) + ... + n! calls.

That can be written as Σ_0≤i≤nn!/i! or (Σ_0≤i≤n1/i!)n! Or (e-1), which is approximately 1.71828 n!

Remains

Thank you for your clear explanation. But can I know why is this algorithm appears? Is this algorithm better than other way to find all possible permutations, or it's just another new way to explore? Thank you. – Muncy

@USER1223_T: I think that's explained on the wikipedia page. ("The algorithm minimizes movement.") I suspect that the guy who thought it up just thought it was cool; that was more than 50 years ago, so I don't know if we'll ever get an answer. I think it's a cool algorithm, for what its worth. – Remains

Answer 2

I think you are confusing between the Heap's algorithm and heapsort algorithm or heap data structure. The later two have O(NlogN) complexity for sorting.

The algorithm you mentioned is for generating all permutations, and because there are N! permutations for every N-element array, the complexity is O(N!).

Unpaidfor

I see, thank you for your explanation. But why would they develop this algorithm for finding all permutations, as the time complexity is still O(N!)? Is this algorithm more efficient if compared to others(normal way to find all other permutations)? – Muncy