test series

Question

consider a set of n distinct numbers by comparison find the 3 largest numbers,

which of the following is true

1.3 largest elements can be found by O(log^2 n) comparisons.
2.O(log^2 n) comparisons is not sufficient but 3 largest can be found in n comparisons.

3.n+O(1) comparisons are needed for 3 largest elements.

4.n+O(1) comparisons are not enough n+O(log n) comparisons are needed.

Answer 1

Is ans D correct?

If yes then I thought by this way!

Build Max heap in O(n) time and then extract 3 maximum elements.

To extract them 1 by 1 and again satisfy max heap property we need to execute MAX Heapify algorithm which is of 3 * log(n) = O(logn)

hence total is n + O(logn)

Comments

Yes, Option D is correct.

---

Hope You've understood the explanation. If not then tell me I'll describe it briefly again. :)

---

Yes, I have understood and your explanation is also correct. You can just remove the first line from your answer(as it creates doubt in readers mind).

---

Thanku...ashwin kulkarni... i got that