9,660 views
49 votes
49 votes

Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE?

  1. These three elements can be determined using $O\left(\log^{2}n\right)$ comparisons.
  2. $O\left(\log^{2}n\right)$ comparisons do not suffice, however these three elements can be determined using $n+O(1)$ comparisons.
  3. $n + O(1)$ comparisons do not suffice, however these three elements can be determined using $n +O(\log n)$ comparisons.
  4. $n+O(\log n)$ comparisons do not suffice, however these three elements can be determined using $O(n)$ comparisons.
  5. None of the above.

7 Answers

Best answer
48 votes
48 votes

Option (C) is correct. Reason is as follows : 

Here, at first level we are Given $n$ elements, out of which we have to find smallest $3$ numbers.

We compare $2 -2$ elements as shown in figure & get $n/2$ elements at Second level.

Note: Minimum element is in these $n/2$ elements.

So, comparisons for this is $n/2$.

Similarly for next level we have $n/4$ Comparisons & $n/2$ elements and so on.

Total Comparisons till now is $n/2 + n/4 + n/8 + \ldots + 4 + 2 +1  = (2^{\log n}-1) = n-1$ {Use G.P. sum}


Now we have to get smallest $3$.

We have 1st smallest at last level already  =>$0$ Comparison for this.

=> $2^{nd}$ and $3^{rd}$ smallest elements can be found in $O(\log n)$ time as shown below:

Minimum Element must have descended down from some path from top to Bottom.


SQUARES represent Candidates for $2^{nd}$ minimum.

Every element that is just below $m_1$ (first  minimum) is a candidate for second minimum.

So, $O(\log n)$ Comparisons for finding second smallest.


Similarly for $3^{rd}$ minimum we get $O(\log n)$ time. As every element that is just below 1st & 2nd minimum is a candidate for $3^{rd}$ minimum.

edited by
25 votes
25 votes

All element are distinct 

1.Using heap
Make a min heap tree                = O(n)
Delete Three element from top   = 3logn
                                                 +
                                                  n + 3logn = n+ O(logn) comparison 
2.Using Selection sort 
3 pass to get three minimum element 
Comparison = n-1+ n-2 +n-3 = 3n-5
Swap           =1+1+1            = 3
                                          +
                                          3n+2
3. for(i=0;i<=n;i++)  // Min1  Min2  Min3 are first 3 element of array  

{
                       if x < Min1 then, Min3 = Min2; Min2 = Min1; Min1 = x;      
                       else if Min1 < x < Min2 then, Min3 = Min2; Min2 = x;
                       else if Min2 < x < Min3 then, Min3 = x;
                       else if Min3 < x skip
}                
Worst case 3n comparision 

4.using Divide and Conquer 

minimum element = n-1 compare 
second minimum  = log2n - 1 compare
third minimum      = loglog2n - 1 compare
total = n+log2n + loglog2n- 3 = n + O(log2n)

So i think three element can be retrieved in O(n){n + O(logn)} time but comparison cant be n + 0(1) since all 3 element can be at     n*(n-1)*(n-2) location and we have to scan the list at least once and compare the to 3 elements.

Option C. 
                             

edited by
19 votes
19 votes
Compare two elements at a time.

$n/2 + n/4 + n/8 + \dots +1 = n $

So, with $n$ comparisons we get the smallest element. The second smallest element must be compared with this smallest element at some point and since we have done $\log n$ levels of comparisons, we have $\log n$ possibility for this second smallest element. Similarly, we have an upper bound of $\log n$ comparisons for the third smallest element- but we need extra space to achieve this time complexity. Option C.
1 votes
1 votes

Answer is (C) part.

PS:

Some analysis of B part.

First create min heap(build max heap). It will take at max 2(n-1) comparison. Now 1st minimum you can get directly(root of the tree). Now 2 and 3 could also be obtained in constant number of comparison( Caution - Do not use extractMinHeap function). 

But (B) part says 'n' it is not O(n). So answer can not be (B) part. Just review others comments for more explanation.

Thanks guys for correcting me.

edited by
Answer:

Related questions