The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes

asked in Algorithms by Boss (13.7k points) | 115 views

1 Answer

+1 vote
Best answer

yes all are correct!

In first case to find the kth largest element, do k-1 deletions from the max heap, so k-1 times max-heapify procedure will be called.

T.C (k-1)logn = O(klogn)

answered by Boss (42.4k points)
selected by


for (ii), i think it will take O(n+klogn)........

since n/2 minimum elements are present in leaves of a max heap, now you have to find kth minimum among them, you can work it like this,

create min heap for that n/2 elements -> O(n)

perform extract_min for k times -> O(klogn)

in total it will take-> O(n+klogn), though if k is some constant, answer will be O(n), but in worst case k can be of O(n)..

therefore i think in worst case to find kth min in max heap will take -> O(n+klogn)

and also one more thing, it might be case that kth min is not even in leaf, because leaf contains about n/2 keys, what if it is saying to find (n/2+5)th minimum..
@Manu Thakur,  Got it.. Thanks a lot :)
@nitish yes you are right answer should b O(n + klogn)

but they explicitly mentioned that k is less than n, and if we believe that it's some constant and n value is huge, we can go for O(n) T.C
but less than doesn't mean that it is some constant, k could be {n-4, n-6 , n/2 , n/4}, all these values are <n and also even O(n)

for that case take all n elements of max heap and build a min heap...and then perform kth min. operation...


@nitish i am not denying this possibility what you said.

yes, exactly i was also saying worst case it will take O(n+klogn)..

it will take O(n) time only when in qsn it is explcitly mentioned that k is some constant.

most appropriate answer then should be (i) and (iii) only...isn't it??
Option (ii) is also okay as K is less than number of element
@Sandeep Suri

please read above comments first.
It's looking for a minimum element in a MAX Heap. Why are you deleting the items here and heapifying again?

In any case it should take maximum O(n) T.C

Related questions

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
49,781 questions
54,511 answers
75,107 users