5,296 views
23 votes
23 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?

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

2 Answers

Best answer
16 votes
16 votes

Answer will be C.

To be accurate, it will need $3n/2 -2$ comparisons .

edited by
8 votes
8 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).

Answer:

Related questions

49 votes
49 votes
7 answers
1