# 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)$$

https://walkccc.github.io/CLRS/Chap06/6.4/ 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)$$.