The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
2.1k views

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 by Boss (29.5k points) | 2.1k views

6 Answers

+25 votes
Best answer

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

3

 

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 & $3$rd smallest can be found in $O(\log n)$ time as shown below:

h

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.

by Boss (15.4k points)
edited by
0
nice explanation @Himanshu 1
0

@Himanshu1

2nd minimum element found in after exactly log n comparissions.

But what about 3rd minimum element?

is it exactly found in log n comparissions ?

i hope NO... it takes 2 log n comparissions,

anyway, i agree it is O ( log n ) only.

0
@shaik brother please explain I am not getting how 3rd minimum will take exactly 2logn HOW?
+2
0
@Shaik brother thanks for making it so easy to understand. Now I got how 2logn comparison for 3rd min. Will it be exact 2logn or 2logn -1 ?
0
i hope it is 2 log(n) - 1.
+1

@  Shaik Masthan  thank u soo much .....i took an example 4 3 2 5 1 6 7 8 10 21 11

the two nodes in first level for 3rd min are  6 and 5???

and in second level  two elements are 3 and 7 ???

please corect if wrong???

0

@eyeamgj,

yes you are correct

0
OK
+16 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. 
                             

by Boss (16.2k points)
edited by
0
Question says 'n', so we cant take 3n.
0
I am taking min - heap as my answer n + 3logn.
0
but to make a min heap?
0
oh yah!! then D should be answer.
0
but answer is C :)
+1
i am working i think using divide conquer is possible !!
0

    Can u explain 4th method ??

    Here how u r taking - second minimum  = log2n - 1 compare
                                      third minimum      = loglog2n - 1 compare

0
When we find 1st min using binary tree there will be n-1 compare and logn level tree now for second min we have to compare to only those element to which 1 is compared in 1st iteration coz second min will among only among them i.e only logn element so compare logn-1 similarly for third min.
0
how lg(lg n) for 3rd minimum
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.
+1
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.
+16 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 Veteran (416k points)
0 votes
Is is some what similar to what himanshu1 stated but calculations required are less

It can be found using TOURNAMENT APPROACH

minimum element can be found using n-1 comparison

2 nd minimum will compare with all those who lost against minimum so it contains n/2 elements

So second minimum can be found in

Log(n/2-1) comparison

Similarly third smallest can be found using Log(Log(n/4-1)) comparison

Total complexity O(n-1 +Log(n/2-1)+(log(n/2-1)+log(n/4-1)) )

Which is equal of O(n+ klogn)

k<n

C should be correct
by Boss (18k points)
edited by
0
Your 1st statement is not correct.  
Minimum can be found in n-1 comparisons,
second minimum n-1+ log n -1 &
3rd minimum
n-1 + log n  -1 + loglog n  -1
0
Oh yes you are correct
0
No I was not fully correct... 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 somecases u will not get right answer.  Thanks Bala.
0
i have to work on algorithm again

Thanks Ahwan
0 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.

by Boss (12.4k points)
edited by
+1

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

0
Please check my comment after his comment.
+2
:) 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.
0
Thanks for correcting me.
–1 vote
ans will be B

construct a min heap and find the smallest 3r d element is O(1)

so total time req is O(n).
by Boss (10.3k points)
+2
n not equal to O(n).
+1
to create a min heap it will take O(n) .

and to find the 3rd  smallest elements we need to check 7 elements from the top . which takes O(1) .

so it will take O(n).
+4
Option B says 'n' and not O(n).
+1

@Arjun Sir, 

Very good observation. But i think some K(here k is 7) no. of comparison could be written as O(1). am i correct ?

Reference -> https://justin.abrah.ms/computer-science/big-o-notation-explained.html

0
good try @Pranay :-)

this doubt should have been cleared to me also that N and O(N) are not the same !!!

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,825 questions
54,735 answers
189,347 comments
80,091 users