The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
closed as a duplicate of: GATE2003-23
asked in Algorithms by (99 points)
closed by | 65 views
extract first elements thats going to take 0(logn) than than repeat the same till 6 steps

you will get it in O(logn)


add the image in the question, why you just keep the link ?


it is a gate question,i hope it is O(1)

yes @shaikh yes it should be 0(1).
sure! i will take care of this definately
guys some are taking out O(1) while some are taking out O(logn)

like in some lectures, we have O(logn) while, Kiran kumar pasupuleti sir has given  we have O(1). so whats the orrect explaination
it can be solved for 0(1) as well as O(logn) it will depend upon the criteria which is  :

1) O(1) if you can easily access elements of the heap. (comparison will be 2^k-1 where k=constant )

2) O(logn) if you can only access the first element of heap.

i think their answer must be different based on the idea of accessing elements of the heap.

it should be O(log n) because

min element will be root takes O(1).

2nd smallest will be at level 1(root is level 0)

3rd smallest element will be at 2nd or 3rd level


similarly 7th smallest element can be found in level 1 to level 6

now we can not do traversal in min-heap or max-heap so first have to delete smallest element then only 2nd smallest element can be found.

after each deletion we have to perform heapify operation which takes O(logn)

so for doing k operation we will require O(k*log n)=O(log n)  

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,534 questions
54,122 answers
71,040 users