Number of comparisons

Question

Comments

O(n)

---

It is A) n+o(logn)

---

how???

---

i think answer should be O(n)   

because for n distinct element in last level we have to do n/2 comparison in second last n/4, n/8....n/2k=1 comparison which is equal to n-1=O(n) comparison

---

Using winning tree method.

---

if we try max heap then last three element will be in leaf node

 

so we need(logn) level +n comparison

---

but @junaid  c should be the answer

---

@ abhishek tiwary how are you getting n ?

---

i have mentioned the comment above@Junaid ahmad

---

i think ...using heap..O(n)+O(logn) ->O(n) should be answer..???    winning tree  is also a form a heap ..and here we can bind the no. of comparison to O(n) but could not say exactly n.

---

Option A is given as answer. please explain how?

---

Yes Option A is correct. Use min heap and then remove first 3 elements which will give smallest 3 numbers.

Time complexity => O(n) for min heap(i.e. n) and then remove 3 elements for that O(3log(n)). => n+O(logn).

---

We can directly do it 3* O(n).  Which comes to O(n) . . Y we r doing like this?

---

@atul_21 I think if we compare both of these approaches.

For 1st => exact complexity => (n + 3log(n)) => roughly O(n).

For 2nd => exact => 3n => roughy O(n).

So both of the approaches are giving O(n) but we have to choose the closest. Then we should choose 1st approach as n + 3log(n) < 3n.

---

Thank u @harish