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

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 Junior (845 points)
edited by | 37 views
0
Brother I'm unable find the question.. Could you please check
0
sry i didnt insert the image :P
0

@Hemanth_13

Fixed it 

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

What was the answer provided.
0
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.
0
Is it nlogn?
0
Yes its O(nlogn)

sorry, i thought it was create heap. my bad

Please log in or register to answer this question.

Related questions

+2 votes
0 answers
1
0 votes
1 answer
2
asked 6 days ago in Algorithms by Shankar Kakde (293 points) | 17 views
0 votes
0 answers
3
asked Jan 4 in Algorithms by jhaanuj2108 (207 points) | 26 views
0 votes
0 answers
4
asked Nov 5, 2018 in Algorithms by nag.swarna (245 points) | 61 views
+1 vote
0 answers
5
asked Jun 11, 2018 in Algorithms by Shankar Kakde (293 points) | 164 views
+3 votes
0 answers
6
asked Jan 20, 2018 in Algorithms by ashish pal Active (1.2k points) | 58 views
+2 votes
0 answers
7


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

47,005 questions
51,325 answers
177,508 comments
66,668 users