0 votes 0 votes closed as a duplicate of: GATE CSE 2003 | Question: 23 https://gateoverflow.in/?qa=blob&qa_blobid=17275535249024428371 Algorithms data-structures algorithms binary-heap + – manvi_agarwal asked Sep 10, 2018 • recategorized Jul 6, 2022 by Lakshman Bhaiya manvi_agarwal 582 views comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments manvi_agarwal commented Sep 11, 2018 reply Follow Share 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 votes 0 votes arvin commented Sep 11, 2018 reply Follow Share 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 votes 0 votes Dharmendra Lodhi commented Sep 11, 2018 i edited by Dharmendra Lodhi Sep 11, 2018 reply Follow Share 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) 0 votes 0 votes Please log in or register to add a comment.