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

you will get it in O(logn)
+1

@manvi_agarwal

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

@arvin

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

0
yes @shaikh yes it should be 0(1).
0
sure! i will take care of this definately
0
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
0
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.
0

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
48,725 questions
52,831 answers
183,518 comments
68,656 users