Dark Mode

makhdoom ghaya
asked
in Algorithms
Nov 19, 2015

7,111 views
47 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.

1

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

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

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.

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

1

2