The Gateway to Computer Science Excellence

+30 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?

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

+28 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 & $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 $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.

0

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.

+5

check this ( url of the image https://drive.google.com/open?id=1CpfFgsZYlnqTMkEUWaPKodrj4xYDq_c6 )

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 ?

+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

i hope NO... it takes

2log ncomparissions

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?

+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 = log_{2}n - 1 compare

third minimum = loglog_{2}n - 1 compare

total = n+log_{2}n + loglog_{2}n- 3 = n + O(log_{2}n)

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.

0

Can u explain 4^{th} 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.

+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.

$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.

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

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

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

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

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

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

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

so total time req is 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).

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

+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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,458 answers

195,367 comments

100,251 users