Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

Problem Detail: 

I am reading section 6.4 on Heapsort algorithm in CLRS, page 160.

HEAPSORT(A)   1 BUILD-MAX-HEAP(A)   2 for i to A.length downto 2   3   exchange A[i] with A[i] 4   A.heap-size = A.heap-size-1   5   MAX-HEAPIFY(A,1) 

Why is the running time, according to the book is $\Theta (n\lg{n})$ rather than $\Theta (n^2\lg{n})$ ? BUILD-MAX-HEAP(A) takes $\Theta(n)$, MAX-HEAPIFY(A,1) takes $\Theta(\lg{n})$ and repeated $n-1$ times (line 3).

Asked By : newprint

Answered By : Juho

Let us count operations line by line. You construct the heap in linear time. Then, you execute the loop and perform a logarithmic time operation $n-1$ times. Other operations take constant time. Hence, your running time is

$\qquad \begin{align} & n + (n-1) \log n + O(1) \\ &= n + n \log n - \log n + O(1) \\ &= \Theta(n \log n). \end{align}$

In other words, as $n$ grows the $n \log n$ term dominates. That is, the cost of building the heap on line 1 is negligible compared to the cost of executing the loop.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4578