3 votes 3 votes Given a set of n distinct integers, it is required to determine the three smallest integers of this array using comparisons, The no of comparison needed are (A) n + O( log n ) (B) n + O( 1 ) (C) O ( n ) (D) O ( log2n ) ANSWER GIVEN ::- A Algorithms made-easy-test-series algorithms sorting madeeasy-testseries-2017 + – VIKRAM KASANA asked Dec 30, 2017 • edited Mar 6, 2019 by Aditi Singh VIKRAM KASANA 1.1k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments pranab ray commented Dec 30, 2017 reply Follow Share here second smallest element is the one which is compaired with first smallest element so comparison goes like that compare (2,3) 3 is second smallest element now see in my eg: third smallest element is compared with first smallest element (worst case)so if you want to find the third smallest element i.e 5 you have to go to last level and we can find only in logn comparison height of tree 0 votes 0 votes Deepak Shinde commented Jan 28, 2018 reply Follow Share I think solution given by them follows min heap property. First build a min- heap by O(n) and then for each minimum perform extract-min using O(log(n)). So total complexity is of the order of O(n) + O(log(n)) 1 votes 1 votes ajay10 commented Dec 17, 2018 reply Follow Share yes, i am thinking in the same way ,since we have to find the smallest three element then we have to build the min heap first which will take o(n) time and after that we need to delete the smallest no. which will take o(logn) time . like this way we will find out all three smallest number in total (n +logn )time 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes construction of build heap it will take n comparisons{minheap} after that you have to delete root element for minimum(you have to replace root will last element of tree it will take log(n) time to maintain heap property ).you have to delete three element it will take time more than 3*log(n).thats why it will take in ans O(LOG(N)) so Total comparisons = N+O(log(n)) in question is not asking for time complexity( in this case ans will be C ). https://gateoverflow.in/190750/ace-test-series-algorithms-sorting Mohit Kumar 6 answered Apr 27, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.