# TIFR2014-B-10

2.5k views

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.
1
suppose n = 1024, exact comparisons required will be $1024*1.5 - 2 = 1534$ (C) is the correct option.
0

What is the explanation for it

1
The divide and conquer algorithm for finding the min and max elements of a list operates in worst case $3n/2 - 2$ comparisons. It is described in Sartaj Sahni's algorithms book.
0
Thanks.
2

To find the smallest and the second smallest element (and the third smallest.. so on), it is $n + O(n)$ (See this and this)

To find the maximum and the minimum element, $ceil(3n/2)-2$

I think answer will be C.

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

edited
10

for even numbers- 1.5n-2

for odd- 3/2(n-1) Comparisions

0
@sushmita

Why n+O(logn) doesn't suffice?
0
It'll need exactly

$2(n-1)-\left \lfloor n/2 \right \rfloor = \left\{\begin{matrix} 3\left \lfloor n/2 \right \rfloor & for \; n \in odd \\ 3n/2 -2 & for \; n \in even \end{matrix}\right.$
0
this formula is not correct for n==2

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

0

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

This is a rather good explanation.

## Related questions

1
4.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? These three elements can be determined using $O\left(\log^{2}n\right)$ ... $O(n)$ comparisons. None of the above.
Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \langle 1,....,n \right \rangle$ is chosen with probability $(1/n!)$ and we inspect the numbers in the order given by this permutation. ... number of times MIN is updated? $O (1)$ $H_{n}=\sum ^{n}_{i=1} 1/i$ $\sqrt{n}$ $n/2$ $n$
Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $c$ by subtracting the smaller number from the larger one. The numbers $a$ and $b$ are put back in the list. If the number ... $273$. What is the score of the best player for this game? $40$ $16$ $33$ $91$ $123$
Consider the following recurrence relation: $T\left(n\right)= \begin{cases} T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if } n=1 \end{cases}$ Which of the following statements is FALSE? $T(n)$ is $O(n^{3/2})$ when $k=3$. $T(n)$ is $O(n \log n)$ ... $T(n)$ is $O(n \log n)$ when $k=4$. $T(n)$ is $O(n \log n)$ when $k=5$. $T(n)$ is $O(n)$ when $k=5$.