Question

What is the time complexity of Heap’s algorithm?

(a) O(n log n)

(b) O(n^2)

(c) O(n*n!)

(d) O(n!)

This question was posed to me by my college professor while I was bunking the class.

My question is taken from Number Theory in portion Number Theory of Data Structures & Algorithms II

Answer 1

Right option is (d) O(n!)

The explanation is: The recurrence relation for the heap’s algorithm is given by the expression T(n)=n * T(n-1). It is calculated by using substitution method. It is found to be equal to O(n!).