15.2k views
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________

edited | 15.2k views
0
seeing the question directly how can one say that which algorithm will give us minimum comparisons?
+1

Notice --> Question is asking minimum number of comparison required and nothing is given about input.

So if some one is thinking about (n-1) then it is not correct. because (n-1) will come if input has some special property.(Here n=100)

So Thanks to @Card Wizard for giving good answer.

+2
0
148
+1
Tournament method is used.

Ans = $1.5n-2 = 1.5*100 -2 = 150-2 = 148$
+1
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.

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

by Active (4.5k points)
selected by
+5

After the first round of Tournament , there will be exactly n/2 numbers = 50 that will loose the round

+6

@Shubhanshu consider 100 players and a match has to be played between two players. Hence matches = 50. Now every match will have a winner(minimum) and loser(maximum). After first set of match, there will be 50 losers, our task is boiled down to selecting biggest loser among losers(50).

0

What if minimum and second maximum was asked?

+1
0

@rohit9 can you explain how you got 197??

0

How did you get 197?? explain.

I'm getting 154

(n-1) + (n/2 - 1) + (log(n) - 1)

99 + 49 + (7 - 1) = 154

after finding 1st maximum, loosers with 1st max should be in log(n) list. so we need another log(n) - 1 comparisons.

+2

See below image. (tournaments are represented with 't', winners as 'w' and losers as 'l')

To find the final winner:

t1 = 50 games = 50 comparisons

t2 = 25 games = 25 comparisons

t3 = 12 games = 12 comparisons

t4 = 6 games = 6 comparisons

t5 = 3 games = 3 comparisons

t6 = 1 game = 1 comparison

t7 = 1 game = 1 comparison

t8 = 1 game = 1 comparison

Total comparisons = 50 + 25 + 12 + 6 + 3 + 1 + 1 + 1 = 99.

To find the final loser:

t1 = 25 games = 25 comparisons

t2 = 12 games = 12 comparisons

t3 = 6 games = 6 comparisons

t4 = 3 games = 3 comparisons

t5 = 1 game = 1 comparison

t6 = 1 game = 1 comparison

t7 = 1 game = 1 comparison

Total comparisons = 25 + 12 + 6 + 3 + 1 + 1 + 1 = 49.

Total comparisons to find minimum and maximum = 99 + 49 = 148.

Edit: I guess this much effort is not required.(I don't know why I was being so silly :P)

It's simply linear comparison. For ex: To find max in the array, initialize the first element as max, keep on updating the max variable by making comparisons with the rest of (n-1) elements whenever a higher number greater than max is encountered. So, number of comparisons is simply (n-1).

0

@chirudeepnamini

Given that we find first maximum, we can find second maximum with just [ceil(log$_{2}$ 50) - 1] comparisons.(This follows from the answer given here) .That would be  [6 - 1] = 5 comparisons.

So, total comparisons needed to find second maximum would be

= No. of comparisons to find first maximum + No. of comparisons to find second maximum

= (50 - 1) + [ceil(log$_{2}$ 50) - 1] = 49 + 5 = 54

0
Great explanation, really quite helpful!! :)
0

@rohit9

It should be 99 + 49 + 24 = 172 comparisons for finding minimum and second largest element.

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

by Active (1k points)
edited
0
If we do not consider divide n conquer:
and the keys are in sorted order, then we can find the min and max in 99 comparisons.Even the iitkgp solutions said that answer is 148 but i dont know why they havent considered the ''99 comparison'' case which is minimum.
0
Min in 99 and max in 99 rt? We can't do both in 99 comparisons rt?
0
we can: suppose the input is in increasing order,then the following code will only take 99 comparisons.

min=max=a[0];
for (i=1;i<100;i++)
{

if (a[i]>=max)
max=a[i];
else
min=a[i];

}
i.e here ,the code will never execute the else part becuz the i/p is in increasing order(non-decreasing order).
+3
We cannot assume a special case for input (it should work for all inputs)

(i.e., we have to find the min. number of comparisons in the worst case)
+2
i thought by min, it meant best case.
like in binary search,
minimum no. of comparisons to find the element is 1.
+6
No. That is the best case. But if question is asked like this, it always means the worst input.
+1
ok.. thanks :)
0
When n is odd what is the number of comparisons?
+2

@arjun sir ,

how you formed below equations

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

+1
Why in the recurrence relation have you added 2 , why not some constant c ?
+12
Here, we are actually splitting up the problem into two small problems, so we have 2T(n/2) , next while combining the results back again, we need to compare the results produced from two sub problems, 1 comparision for max element and other comparision for min element..
0
if you take a small example and see, for example 6 elements, you will notice it takes 2*(n-1) = 2*5 = 10 comparisons. Which is the same as linear approach. But the recurrence relation approximates some values. Example T(5) = 2T(2) + 2. Instead of T(3) + T(2) + 2

Let me explain this in detail. Consider 6 elements

T(6) = 2T(3) + 2

= 2(T(2) + T(1) + 2) + 2

= 2 (2 + 0 + 2) + 2

= 2*4 + 2

= 10

But due to approximations in when we computes T(n) = 3n/2 -2

we get T(6) as 3*6/2 -2 = 7.

Hence actual answer will be 2*(n-1) for 100 elements, which is 198 instead of 148.
+2
can any one please solve the recurrance. not able to find 3/2n-2
+1
Hi. It is the average case. Therefore it's 1.5n-2
+1

@Arjun sir would you please tell me how we are getting 3/2n-2  from recurrence equation

0
@arjun Can we use extra O(logn) memory here?If yes then the answer should be n + ceil(logn) - 2 considering we keep track of the nodes that lose to the smallest element which will be at max logn.
0
@Hcas Hgnis

The maximum number of comparisons in your code will be  (2n-2).

So, the average number of comparisons will be

[(n-1)+(2n-2)]/2

(3n-3)/2

1.5(n-1)

1.5(99)

149

Can we solve this like that?
0
If number are already sorted then why do we even need comparison.We can directly say first element is min while last is max?
+1

@kshitij Yes but why would you consider sorted case. See Arjun Sir's comment above.

0
Isn't it supposed to be 3n/2 instead of 3/2n?
0
someone please solve that recurrence relation and show it here, not getting (3/2)n-2
+1

@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

0

thanks @vizzard110

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]

by Active (5k points)
0
thanks

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$

by Loyal (5.7k points)
edited
+2
what if we have total numbers in odd
+3

The most complete explanation of Tournament method. Thanks.

+2
This is a great underrated answer.
+1

best answer thanks @Rishav Kumar Singh

0
2 ^-logn is 1/n ? how you reduced. i cant understand
0
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

The answer is based on computing minimum and maximum in pairs of two

say number of elements in even and array is

5 1 2 5 6 8 9  10

than code goes as follows

fun(){

int mn,mx;

if(arr[0]>arr[1]){  mn=arr[1];mx=arr[0];} // 1 comparison for 2 elements

else{ mx=arr[1];mn=arr[0]; }

for(int i=2;i<n;i=i+2){ // picking every  pair of element

// we will calculate the minimum and maximum of this pair and then compare with global minimum and maximum hence total of 3 comparisons for a pair

int t_mn,int t_mx;

if(arr[i]>arr[i+1]){ t_mn=arr[i+1]; t_mx=arr[i];} // 1st comparison

else {  t_mn=arr[i]; t_mx=arr[i+1];}

if(mx>t_mx) mx=t_mx; // 2nd comparions

if(mn<t_mx) mn=t_mx; // 3rd comparioson

}

cout << mx << " " <<  mn << endl;

return 0;

}

hence if n is number of elements

than comparisons=1+((n-2)/2)*3

hence in n=100 ans=148

similarly in odd number of elements 1st element will be max as well as min

hence comparisons=((n-1)/2)*3

refer to CLRS book

by (421 points)
+1
please explain how u solve this recurrence relation
Algorithm for finding minimum and maximum:

If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first two elements
respectively.
For rest of the elements, pick them in pairs and compare their
maximum and minimum with max and min respectively.

this is  same as the tournament method .

So when n is odd, number of comparisons = 3*(n-1)/2
when n is even, number of comparisons = [3*(n)/2] - 2 = 3*50-2 = 148.
by Active (2.2k points)

Consider n=8 elements in an array {1,4,5,8,3,2,7,9}
Lets make a tournament bracket for them, where at each stage the winner is the minimum element between the two.

As you can see, number of comparisons being done = n-1 = 7

Similarly, to find the maximum element you again will need n-1 comparisons!
So total no of comparisons to find min and max=2(n-1)
Hmm...there is one optimisation to it !!

The last level in the tree is making n/2 comparisons(4 in this case) and these are being repeated while finding the minimum and maximum!

So doing the last level comparisons only once, we do n/2 comparisons less
Hence 2(n-1) - n/2 = 2n-2-n/2 = 3n/2-2.

So, here n= 100

Using 3n/2-2 = 150-2 = 148

by Active (2k points)
by Active (1.2k points)