0
$\begingroup$

I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows:

1. Build a max-heap out of the unsorted array, say A. (O(n))
2. Exchange root of the heap (max element in the heap) with the last 
   element of the heap.
3. Decrement the heap size by 1.
4. Run MAX-HEAPIFY on A(1).
5. Keep repeating steps 2-4 until all elements have been sorted.

The step 3 takes time O(lg m), where m is the current size of the shrinking heap being max-heapified (m ranges from (A.length - 1) to 2). So the total time taken max-heapifying would be Σlg(n - j) where the summation runs from j = 1 to j = n-2. So the total time taken would be lg((n-1)!). We know that lg((n-1)!) < nlgn. So how can nlgn be the lower bound? (It should be lg((n-1)!) as per the above). Its ok if we are talking about the upper bound since nlgn is greater always, and we can say that heap sort in worst case takes O(n lg n).

I understand that the algorithm can have worst-case running time that is both O(nlgn) and Ω(nlgn); the former specifying an upper bound, and the latter the lower bound. What I understand is that the if runtime is Ω(nlgn), it means that the algorithm will take time of the order of nlgn lower bound. My question is different. The time taken in case of heap sort should Σlg(n - j), summing all the run times of max-heapify instances, which comes out to be lg((n-1)!. So heapsort in the worst case should have a run time of Ω(lg((n-1)!) instead of Ω(nlgn) ; also lg((n-1)!) < nlgn (since nlgn = lg (n raised to n)) Please correct me if wrong.

$\endgroup$
  • $\begingroup$ There's no such thing as "the upper bound", just as there's no such thing as "the integer bigger than 10." There are infinitely many of both. $\endgroup$ – David Richerby Mar 13 '18 at 17:58
2
$\begingroup$

An algorithm can have worst-case running time that is both $O(n \lg n)$ and $\Omega(n \lg n)$; those don't contradict each other. See How does one know which notation of time complexity analysis to use? and https://cs.stackexchange.com/a/201/755 for some background that might help understand why that is so.

$\endgroup$
1
$\begingroup$

Note

$$\log (n-1)!\ge \log \frac{n-1}{2}+\cdots+\log (n-1)\ge\frac{n-1}{2}\log \frac{n-1}{2}=\Theta(n\log n).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.