Question

"What is the running time of HEAPSORT on an array A of length n thatis already sorted in increasing order?

Answer 1

The answer to this question is O(NlogN).

Step-by-step explanation:

The time complexity of Heap Sort on an array A is O(NLogN) even if the array is already sorted in increasing order.Since the Heap Sort is implemented by creating the heap from the array and then heapifying and then repeatedly swapping first and last element and deleting the last element.The process will be done for the whole array.So the running time complexity is O(NLogN).