6.4-4

Show that the worst-case running time of HEAPSORT is $\Omega( n lg n)$.

The worst case occurs when we have move the root element to the leaf the running time is for MAX-HEAPIFY is $\theta (h)$ = $\theta(log n)$
Heap sort calls MAX-HEAPIFY n-1 times.
$$ \sum_2^n \theta (log n) $$ $$ \theta( \sum_2^n log n) $$ $$ \theta( log 2+log 3 + ...log n) $$ $$ \theta(log n!) $$ $$ \theta(n log n) $$ hence the worst case running time is $\Omega( n lg n)$