0 votes 0 votes atul_21 asked Nov 13, 2017 atul_21 533 views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply Rishabh Gupta 2 commented Nov 13, 2017 reply Follow Share O(n) 0 votes 0 votes junaid ahmad commented Nov 13, 2017 reply Follow Share It is A) n+o(logn) 0 votes 0 votes akash.dinkar12 commented Nov 13, 2017 reply Follow Share how??? 0 votes 0 votes abhishek tiwary commented Nov 13, 2017 reply Follow Share 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 0 votes 0 votes junaid ahmad commented Nov 13, 2017 reply Follow Share Using winning tree method. 0 votes 0 votes abhishek tiwary commented Nov 13, 2017 reply Follow Share if we try max heap then last three element will be in leaf node so we need(logn) level +n comparison 0 votes 0 votes abhishek tiwary commented Nov 13, 2017 reply Follow Share but @junaid c should be the answer 0 votes 0 votes junaid ahmad commented Nov 13, 2017 reply Follow Share @ abhishek tiwary how are you getting n ? 0 votes 0 votes abhishek tiwary commented Nov 13, 2017 reply Follow Share i have mentioned the comment above@Junaid ahmad 0 votes 0 votes hs_yadav commented Nov 13, 2017 reply Follow Share 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. 0 votes 0 votes atul_21 commented Nov 13, 2017 reply Follow Share Option A is given as answer. please explain how? 0 votes 0 votes Harish Kumar 2 commented Nov 13, 2017 reply Follow Share 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). 1 votes 1 votes atul_21 commented Nov 14, 2017 reply Follow Share We can directly do it 3* O(n). Which comes to O(n) . . Y we r doing like this? 0 votes 0 votes Harish Kumar 2 commented Nov 14, 2017 reply Follow Share @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. 1 votes 1 votes atul_21 commented Nov 14, 2017 reply Follow Share Thank u @harish 0 votes 0 votes Please log in or register to add a comment.