CODEWITHSUNDEEP
algorithmheapasymptotic-complexityheapsort
lalatnayak
lalatnayak

Reputation: 170

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?

Upvotes: 2

Views: 1671

Answers (2)

rici
rici

Reputation: 241931

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

Upvotes: 3

orlp
orlp

Reputation: 117886

Big O notation notates an upper bound. As you've said:

MAX-HEAPIFY has a complexity of O(h) where h is the height of the heap which has a max value of log n.

We don't care if the heap gets smaller. We know that at worst, the heap has height log n. We do this n times, hence n log n.

Upvotes: 3

Related Questions