edited by
53,589 views
89 votes
89 votes
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
edited by

16 Answers

Best answer
124 votes
124 votes

We can solve this question by using Tournament Method Technique -

1. To find the smallest element in the array will take $n-1$ comparisons $= 99.$

2. To find the largest element - 

  1. After the first round of Tournament , there will be exactly $n/2$ numbers $= 50$ that will loose the round.
  2. So, the biggest looser (the largest number) should be among these $50$ loosers.To find the largest number will take $n/2 - 1$ comparisons $= 49.$

Total $99+49 = 148.$

selected by
72 votes
72 votes

Ans: minimum number of comparison require to find minimum and maximum is: Approach is divide and conquer ....

  T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 
  T(2) = 1 // if two element then compare both and return max and min
  T(1) = 0 // if one element then return both max and min same

  If $n$ is a power of $2$, then we can write $T(n)$ as:

   T(n) = 2T(n/2) + 2 

  After solving above recursion, we get

  T(n)  = (3/2)n - 2 

 Thus, the approach does $(3/2)n -2$ comparisons if $n$ is a power of $2$. And it does more than $(3/2)n -2$ comparisons if $n$ is not a power of $2$.

So, here in this case put $n=100$ and we will get $(3/2)(100) - 2 = 148$ comparison .....

edited by
56 votes
56 votes

NOTE: At level 1 in $\frac{n}{2}$ comparisons we are finding Both MINIMUM as well as MAXIMUM for level 2.  

Let's see for minimum,

At level 1 :$\frac{n}{2}$ comparisons

At level 2 : $\frac{n}{2^2}$ comparisons

At level 3 : $\frac{n}{2^3}$ comparisons

so on.... 

At level logn : $\frac{n}{2^{logn}}$ comparisons

So, Total number of comparisons will be 

$\frac{n}{2}$ +  $\frac{n}{2^2}$ +  $\frac{n}{2^3}$ + .....+ $\frac{n}{2^{logn}}$

$\Rightarrow$ n ($\frac{1}{2}$ +  $\frac{1}{2^2}$ +  $\frac{1}{2^3}$ + .....+ $\frac{1}{2^{logn}}$ )   [apply Sum of G.P]

$\Rightarrow$ $n\frac{1}{2}(\frac{1-(\frac{1}{2})^{logn}}{1-\frac{1}{2}})$

$\Rightarrow$ $n\frac{1}{2}(\frac{1-(2)^{-logn}}{\frac{1}{2}})$

$\Rightarrow$  $n(1-\frac{1}{n})$

$\Rightarrow$  $n-1$

So,total comparisons required to find minimum of n element is n-1 comparisons.

similarly for Max n-1 comparisons required.

So total comparisons for both min and max will be

$2(n-1) - \frac{n}{2}$     $\Rightarrow$ $\frac{3n}{2}-2$   

 [ $\frac{n}{2}$ is reduced because at Level 1 we have taken $\frac{n}{2}$ for both while min and max calculation ]

coming to question n = 100,

total comparisons $\Rightarrow$ $\frac{3 * 100}{2}-2 =  148$   

 

 

46 votes
46 votes

Tournament Method Technique(Easy Method by example)

For example we have 8 elements [1,4,5,8,3,2,7,9]

Step-1: Make buckets of 2 elements:: (1,4) (5,8) (3,2) (7,9)

Step-2: Find Minimum and Maximum from this buckets, and make both side expanding tree like this,

Step-3: So you need (n-1) comparisons for finding either minimum or maximum

Step-4: first (n/2) comparisons only needed once.

Step-5: So total(Minimum+Maximum): 2*(n-1)-(n/2) = [3*(n/2)-2]

Answer:

Related questions

0 votes
0 votes
1 answer
2
Raghav Khajuria asked Oct 13, 2018
322 views
Minimum no of comparisons required to find the minimum and maximum of n distinct elements
1 votes
1 votes
1 answer
3
mystylecse asked Aug 15, 2017
3,449 views
The minimum number of comparisons required to find the minimum and maximum of 60 numbers is..............
0 votes
0 votes
1 answer
4
Aspi R Osa asked Dec 14, 2015
1,509 views
Consider a set of 20 elements.To find maximum and minimum element in the given set, the minimum number of comparisons required is _________? (using DAC Max-Min algorithm)...