11 votes

Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE?

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

12 votes

7 votes

Similar to the approach proposed by Himanshu1 here:

https://gateoverflow.in/27194/tifr2014-b-9

Construct a decision tree to determine the* minimum* element: $n - 1$ comparisons

*Maximum* element can be found from the same tree as it will be the *biggest *element out of $\frac{n}{2}$ elements at the first level which *lost* the* *decision: $\frac{n}{2} - 1$ comparisons

Therefore, the resultant number of comparisons: $3(\frac{n}{2}) - 2$, tighest bound on which is **option (C)**.

0

@pranav Kant Gaur

Maximum element will at leaf na? and at leaf there are n elements so comparison should be n-1. Please clear my doubt.

Maximum element will at leaf na? and at leaf there are n elements so comparison should be n-1. Please clear my doubt.

0

Yes maximum comparison will be for leaf.But question is asking for both maximim and minimum .

For maximum n-1 comparison

For minimum n-1 comparison

Total number of comparison=2*(n-1)

If you will draw the tree you will find that the leaf node level(is the last level) needs n/2 comparison.And it is common to both minimum and maximum.

So total number of comparison required=2*(n-1) -n/2 =(3/2)n-2 when n is even.