The Gateway to Computer Science Excellence

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

+10 votes

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

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

50,737 questions

57,370 answers

198,506 comments

105,276 users