in Algorithms
9,886 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.
in Algorithms
9.9k views

4 Comments

We can build min heap whose time complexity is O(n) and we can apply extract min three times to get 3 minimum number.
1
1

@BASANT KUMAR question is about number of comparisons not about time complexity 

0
0

Timecomplexity = no of comparisons +no of swaps you made for any sorting algo,so basically any comparison sort ,time complexity is based upoon how much comparisons you made and how much swaps you do,so i think @BASANT KUMAR right.

0
0

7 Answers

48 votes
48 votes
Best answer

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

4 Comments

SHAIK MASTHAN ALONG WITH 3,5,6,7 ELEMEMTS THAT LOST TO 1ST ELEMENTS ALSO GETS INCLUDED IN THEM RIGHT LIKE HERE OTHER THESE ELEMENTS 10 IS ALSO DIRECTLY DEFEATED BY 1 SO COMPARISONS AMONG 3,5,6,7,10 TAKES PLACE RIGHT?? 

 

0
0

@JEET

for the first minimum it took (n-1) comparisons that’s why n+logn.

0
0

For first min we need (n-1)comparisons. I understood this.

But for second, I think we need log(n)-2 comparisons and for 3rd we need 2log(n) -2 comparisons.

Because, for second element we have only log(n)-1 elements to compare and to compare them we need log(n)-2 comparisons. Please correct me where I’m wrong !

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

4 Comments

how lg(lg n) for 3rd minimum
0
0
for third min we have left with loglogn elements. coz we have to compare among them only to which second min is compared tree level will be loglogn.
0
0
edited by
3rd term is not log log n.. You have to include those who lost from 1st in 1st round + those who lost from 2nd in first round too..take 16 numbers & check...otherwise in some cases u will not get right answer.  Thanks Bala.
7
7
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.
by
1 vote
1 vote

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

4 Comments

@Chhotu..You really don't read entire discussions :(

Your doubt have already been answered by Arjun sir above.

n not equal to O(n).

Option B says 'n' and not O(n).

1
1
reshown by
Please check my comment after his comment.
0
0
:) you are not getting it.

See O(N) can be = 2n or 3n or 10000n or 1200000000n  in general <=constant n

Now build heap =O(n) is not necessarily equal to n it can be any of the above.

PS: Constant comparisons=O(1) is not the point here.
2
2
Thanks for correcting me.
0
0
Answer:

Related questions