Question

What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?

1. $\Theta(1)$
2. $\Theta (\log n)$
3. $\Theta (n)$
4. $\Theta (n \log n)$

Comments

It is constant.as long as number is independent of n it can be found with k×k-1/2

Comparisons.

---

$\Theta \left ( logn \right )$

---

what if they have asked for the upper bound for the number of comparisons? then will it be 0(n) 

@Anurag_s   

@Arjun sir

Answer 1

Finding minimum element in a min heap takes O(1) time. To find the 50th smallest element in a min heap needs to delete first 49 smaller elements and then finding the next smaller element, i.e. 50th smallest element. 

Deleting smallest element (root element in a min heap) takes O(logn) time. Total time to delete 49 smaller elements is O(49*logn) = O(logn). Next finding the next min element takes O(1) time. 

Next inserting all the 49 deleted elements need to be inserted back into the heap. That takes O(49*logn). The total time complexity thus becomes O(logn).