edited by
1,027 views
1 votes
1 votes

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?

edited by

Please log in or register to answer this question.

Related questions

1 votes
1 votes
1 answer
1
LavTheRawkstar asked Sep 9, 2018
1,030 views
Sort The Following Sequence of input using Heap sort.{ 10 , 2 , 1 , 5, 3 ,8 ,11,24 ,7 }Please show the output at every pass because i am getting confused.
0 votes
0 votes
1 answer
2
Balaji Jegan asked Jun 18, 2018
565 views
Would it be possible to implement a variant of heapsort based on a perfectly balanced ternary structure in which the children of node $i$ are at positions $3i - 1, 3i$, a...
1 votes
1 votes
1 answer
4
reena_kandari asked Jul 30, 2016
987 views
The number of elements that can be sorted in time using heap sort ?