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.

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!

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