MadeEasy Test Series 2017: Algorithms - Sorting

Question

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

Comments

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

---

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))

---

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

Answer 1

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