Question

2.) Consider an input array A of size n in which n − 1 of the elements have identical values and the remaining one value is smaller than the n − 1 identical values. What is the running time of Heapsort with input A?

Answer 1

2) The running time of Heapsort with input A will be O(n log n).

Heap sort requires two steps. One is creating the tree and the other one is heapify process. As we already know that, apart from one element other elements are identical to each other. So, the heapification process will run for that element and the complexity will be O(n log n). If all the elements in the array were identical then it will take O(n) times as no heapification will be required. In that case only traversing the tree will be required which will take O(n) time. But, since one element is smaller than all other equal elements, so we will require the heapification. So, it will take O(n log n) time.

Please comment in case of any doubt.
Please upvote if this helps.