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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

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

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

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.

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.

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.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,756 questions

52,850 answers

183,548 comments

68,745 users