0 votes 0 votes What is the number of comparisons required to extract 45th element of the min heap? Algorithms algorithms binary-heap time-complexity + – bts1jimin asked Sep 10, 2018 bts1jimin 1.8k views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply srestha commented Sep 10, 2018 i edited by srestha Sep 10, 2018 reply Follow Share O(1) or$\left ( 2^{45}-1 \right )$ if it is min heap and u r searching from root 1 votes 1 votes Rustam Ali commented Sep 10, 2018 reply Follow Share @srestha please elaborate 0 votes 0 votes srestha commented Sep 10, 2018 reply Follow Share As here 45 i.e. a constant value is given , comparison will also be constant right? 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share mam, i hope his ( Rustam Ali ) doubt is, how you say it is ( 245 - 1). Bye the way did you assume the root height = 1 ? 0 votes 0 votes srestha commented Sep 10, 2018 reply Follow Share @Shaik why height will need here? We only need no of comparison 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share then how you got 245 -1 0 votes 0 votes srestha commented Sep 10, 2018 reply Follow Share @Shaik draw this heap tree 1,4,2,5,6,7,3 See the number of comparison to find 3rd minimum is $2^{3}-1$ or not?? 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share that is in-directly referring height, when height of root=1 if height of root=0, then it would be 2(h-1) - 1 0 votes 0 votes srestha commented Sep 10, 2018 reply Follow Share or u can say level 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share sorry mam, it is level only... by taking height it will create more complexity 0 votes 0 votes srestha commented Sep 10, 2018 reply Follow Share for height it will be $2^{h+1}-1$ 0 votes 0 votes Sankha Narayan Bose commented Sep 10, 2018 reply Follow Share Time complexity will not be O (logn)????? @srestha 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share it is bonded ===> O(1) https://gateoverflow.in/1110/gate2003-23 0 votes 0 votes neerajyadav commented Dec 4, 2018 reply Follow Share for the 45th minimumm in heap total uumber of comparisons =sum of first 44 natural numbers=44*45/2=990 1 votes 1 votes Somtirtha commented Dec 10, 2019 reply Follow Share why how ? 0 votes 0 votes Please log in or register to add a comment.