2.2k 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.
| 2.2k views

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 & $3$rd smallest 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 m1(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.6k points)
edited
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?
+5
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 ???

0

@eyeamgj,

yes you are correct

0
OK
0

@Shaik Masthan

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

u means after extracting 1st minimum, we can get 2nd minimum. So, extracting 1st minimum will take logn time and extracting 2nd min, takes logn tim. So, total logn+logn=2logn time. right?

0

we have n elements, so 1st smallest found in n-1 comparison.

2nd smallest found in logn - 1 comparisons

3rd smallest found in log(logn) - 1 comparison.

Is it like that ???

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.4k points)
edited
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
+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.
+2
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.
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 (424k points)
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 (18.3k 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

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 (13.3k points)
edited by
+1

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

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.4k 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 ?

0
good try @Pranay :-)

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