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.
