The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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

  1. 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?

asked in Algorithms by Active (1.3k points)
edited by | 50 views
Brother I'm unable find the question.. Could you please check
sry i didnt insert the image :P


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

Please log in or register to answer this question.

Related questions

+1 vote
0 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
68,745 users