GATE CSE 2003 | Question: 23

Question

In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time

• A. $\Theta (n \log n)$
• B. $\Theta (n)$
• C. $\Theta(\log n)$
• D. $\Theta(1)$

Comments

why not $log_2(n)$?

if $log_2(n)$ comes into your mind, implies you where thinking just perform extract_min() operation 7 times

well doing this changes the min heap, the goal was to just find the 7th smallest element

for instance, to view the 7th element of a stack, you don't pop() 7 times and then print

---

panipuri

So it's like a fixed fact that for a min heap, the kth element cannot be beyond k-1 th level....So however large the min heap is, we always know the number of levels we need to search(constant) if asked for kth min...Am I correct?

 

---

Yes, you are correct unless the node in question is repeating in the heap.

Answer 1

In a min-heap, smaller numbers stay near the top, and larger numbers sit below them.<!--TgQPHd|||[]-->

• The 1st smallest element is always at Level 1 (the root)
• The 2nd smallest element must be right below it, at Level 2
• The 3rd smallest element will be nearby, at Level 2 or Level 3

Following this pattern, to find the 7th smallest element, you never have to look deeper than Level 7

So the number of nodes from level 1 to level 7 remain constant so the answer is \(\Theta(1)\)

Answer 2

The question is quite ambiguous.

If the question means

i) it's a min-heap then answer would be O(1), because at worst case we need to check the roots at depth 7, and as we know asymptotic complexity tells the order of growth of time wrt 'n' or input size, here irrespective of n, if it's greater than 7 we only need to check at depth 7 at worst case as I said, even if n is 10, 100, 1000 and so on. So, it's not depending on 'n'.

ii) it's just a binary tree with the least element at the root of the tree then T would be O(nlogn) because at worst case we need to search the entire tree.

Answer 3

All the answers above are correct and very clear but if you have any confusion, and would like a programming approach,

Think of how you can write a program for it. For example, In a min heap, you know that the 3rd  smallest element would be located at left or right of the root so you can hardcode a function like

min(root->left, root->right)

Similarly you can also hardcode a function for 7th smallest element because YOU KNOW before hand that it is located among the first 7 levels and write a function that runs over some say k elements and finds a minimum.

No matter the size of N, a 1000 elements or a billion elements in that min heap, your code always takes K(constant) amount of time and doesn’t grow proportionally to N.

So answer is Θ(1)

Answer 4

Answer is option B,​​​​​​

Explanation:-

We know in binary heap the minimum element is always at the root position

Time to get minimum element is O(1).

And TC of deleting min and forming min heap again is O(logn)

Therefore, for finding 7th smallest element we have to delete element from heap 7 times.

Therefore, TC = O(7logn) = O(logn)

Comments

WRONG ANSWER!!
 

Answer 5

The search of 7th smallest element is independent on the input size n so it takes constant time for every input n  O(n)

Comments

As heap is minheap already indicating the question as smallest element at the root so to find the 7th smallest from that minheap it will take O(1)  i.e. theta(1) time so (d) is correct.

---

if question is about to find n^th smallest element then it will be O(n)???????

---

lg(n)