in Algorithms edited by
44,166 views
72 votes
72 votes
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
in Algorithms edited by
44.2k views

4 Comments

Tournament method is used.

Ans = $1.5n-2 = 1.5*100 -2 = 150-2 = 148$
4
4
If $n$ is $odd=3$$\left \lfloor \dfrac{n}{2} \right \rfloor$

If $n$ is $even=$ we perform $1$ initial comparison followed by $\dfrac{3}{2}(n-2)$ comparisons, for a total of $\dfrac{3n}{2}-2$ comparisons

$Ans:\dfrac{3\times 100}{2}-2=148$

 

Reference : Chapter 9, Medians and order statistics, cormen.
14
14

Here you go

what kushagra is saying

8
8

14 Answers

106 votes
106 votes
Best answer

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

4 Comments

They have asked for the minimum number of comparisons, so shouldn’t it be best case of max min algorithm which happens when array is sorted. In that case overall n-1 comparisons would be required to find both max and min? Why are we trying to find the worst case number of comparisions?
0
0

@Tmajestical No. They didn’t say that array is sorted. Hence, we need to give generalized answer which is achieved only through Tournament Method. We can’t assume sorted array here.

0
0
edited by

@Abhrajyoti00, I agree with you, they have not specified that the array is sorted. But they were asking for minimum number of comparisons, which means best case, and best case of max-min will occur when array is sorted. Which is why I have considered a sorted array. 3n/2 -2 is fine, but it would be the average case of the standard max min algorithm or for an optimized version, it may be the worst case (upper bound).

0
0
70 votes
70 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

4 Comments

@akshay7797 see this link I was also confused in solving this recurrence relation

https://math.stackexchange.com/questions/2829507/solve-the-recurrence-tn-2-tn-2-2

 

2
2
0
0

here it says the best case, not minimum so why not 199?

0
0
52 votes
52 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$   

 

 

edited by

4 Comments

2 ^-logn is 1/n ? how you reduced. i cant understand
1
1
From the properties of logarithms

2^log n = n

Hence 2^-logn can be written as 2^log(n^-1) = n^-1 = 1/n
0
0
Indeed best answer.
0
0
43 votes
43 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]

2 Comments

thanks
0
0
what would be the approach for second min and max?

answer would be?

99+49(min)?
0
0
Answer:

Related questions