Question

What is the average number of comparisons used in a heap sort algorithm?

(a) N log N-O(N)

(b) O(N log N)-O(N)

(c) O(N log N)-1

(d) 2N log N + O(N)

The question was posed to me during an interview.

This is a very interesting question from Heapsort in section Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (d) 2N log N + O(N)

The best I can explain: The average number of comparisons in a heapsort algorithm is mathematically found to be 2N log N + O(N).