Show that the worst-case running time of HEAPSORT is \(\Omega(n \lg n)\).
This is the case in which each call to MAX-HEAPIFY requires traversing the entire height of the heap which is already bound by the runtime described in Exercise 6.4-3.
Show that the worst-case running time of HEAPSORT is \(\Omega(n \lg n)\).
This is the case in which each call to MAX-HEAPIFY requires traversing the entire height of the heap which is already bound by the runtime described in Exercise 6.4-3.