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

@SatyamK Heapsort takes $O(n log n)$ time, which is inefficient for this purpose

---

D

---

we are doing asymptotic analysis here and 7^th smallest element will be present within 6^th level(some constant number of nodes will be present) now if we take n as very large number then number of elements we need to compare becomes constant so answer is D.

Answer 1

1^st minimum will always at root of min heap. Hence 0 comparisons.

Now 2^nd minimum can be child left child or right child of the root. Hence 1 comparison.

For the 3^rd minimum we are assuming that 2^nd min is the left child of root. So the 3^rd minimum must be in the childs of 2^nd min or right child of 1^st min(root). Because if 3^rd min is found other places than these nodes then min heap property will be violated (try yourself by some examples). So total comparison 2.

Now same way I am assuming the 3^rd min is the left child of the 2^nd min so the 4^th min can be found in the the area in the picture below. So to find 4^th min we have to compare 4 nodes means 3 comparisons.

You can try the remaining yourself.

1^st min → 0 comp

2^nd min → 1 comp

3^rd min → 2 comp

4^th min → 3 comp

5^th min → 4 comp

………

……….

k^th  min → k-1 comp

To finnd k^th min we need k*(k-1)/2 comp.

So to find 7^th min we need 7*(7-1)/2 = 21 comp.

So time needed $\Theta$(1).

Option: D 

 

Answer 2

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)