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 (nlg{n})$ rather than $Theta (n^2lg{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
