6.4-3

6.4-3 What is the running time of HEAPSORT on an array A of length n that is already sorted in increasing order? What about decreasing order? No effect. Either way Build-MAX-HEap will take $O(n)$ to build a max heap. The running time of a heap sort take n-1 calls to max-HEAPIFY (takes log n time) $$\sum_2^n log n $$ $$ log 2+ log 3+.....log n $$ $$ log n! $$ by Stirling approximation above eq is $$ O(n log n)$$