algorithmheapasymptotic-complexityheapsort

Heap Sort Complexity

Below is the Pseudo Code of HEAPSORT on an array

HEAPSORT(A)
  BUILD-MAX-HEAP(A)
  for i = A.length downto 2
     exchange A[1] with A[i]
     A.heapsize = A.heapsize - 1
     MAX-HEAPIFY(A,1)

It is clear to me that BUILD-MAX-HEAP has a complexity of O(n) and MAX-HEAPIFY has a complexity of O(h) where h is the height of the heap which has a max value of logn.

What I don't understand completely is why does HeapSort have a complexity of nlogn. I understand we have n iterations with each a MAX-HEAPIFY. But he MAX-HEAPIFY call gets a HEAP of diminishing size in each iteration. How can then each iteration have a complexity of O(lgn)? Is it tightly bound? Any where I can see the mathematical proof of the same?

Solution

  • Observe that

    log 1 + log 2 + log 3 + ... + log n
= log (1 * 2 * 3 * ... * n)
= log n!

    Now, by Stirling's approximation,

    n! ≈ sqrt(2πn) * (n/e)n

    So:

    log n! ≈ n * (log n/e) = n * (log n - 1)  = n log n - n

    which is O(n log n) because the n log n term dominates the n term (and the O(log n) term I left out because it is too hard to type withou MathJax).