CLRS Exercise 6.4-5

The question is as follows: Show that when all elements are distinct, the best-case running time of HEAPSORT is $ \Omega(n\lg n)$ This website provides a rather complicated analysis to this question, but the obvious answer that occurred to me was far simpler. Hoping if anyone can check if it is correct.

Since the height of a filled n-element tree is $ \lfloor \lg n \rfloor$ , the minimum number of swaps in one run of heapify would be the minimum distance from the root of the tree to a leaf node of the tree, i.e. min swaps $ \geq \lfloor \lg n \rfloor – 1\geq \lg n – 2$ . Hence, the summation $ \sum_{i=1}^{n}\lg i – 2=\Theta(n\lg n)-\Theta(2n)=\Theta(n\lg n)$ , which implies $ \sum_{i=1}^{n}\lg i – 2=\Omega(n\lg n)$ .