Ace Test Series: Algorithm - Heap Sort

Question

Q : What is the running time of heap sort for presorted input of size n?

• A. O(n)                  B) O(n^2)              C) O(nlogn)               D) O(logn)

In the question they didn’t mention if its a max or min heap and also they didn’t mention if the “presorted” input is in ascending or descending order.

For example, if we take max heap, if the order of input is decreasing order, the time complexity would be O(n) and for decresing order it would be O(nlogn).

Is the question incomplete or am i missing some concepts?

Comments

Brother I'm unable find the question.. Could you please check

---

sry i didnt insert the image :P

---

@Hemanth_13

Fixed it 

---

I think though it is sorted we have to build heap and delete an element and reheapify ==> O(nlogn)

What was the answer provided.

---

heap sort works impartially for all the worst, best as well as average case, and it is O(nlogn).

it will always do these 3 steps--

1) build (min/max) heap

2) for i=length(heap) down to 1

        delete A[1] and A[i]

        decrement the size of heap by 1

        min/max heapify.

No Concession will be there for sorted array.

---

Is it nlogn?

---

Yes its O(nlogn)

sorry, i thought it was create heap. my bad