The Gateway to Computer Science Excellence
+48 votes
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
in Algorithms by Veteran (104k points)
edited by | 13.5k views
seeing the question directly how can one say that which algorithm will give us minimum comparisons?

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.


11 Answers

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

by Active (4.4k points)
selected by

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

How it is, please explain?? 


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


@tusharp What if minimum and second maximum was asked?

197 will be answer

@rohit9 can you explain how you got 197??


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.

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

by Active (1k points)
edited by
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.
Min in 99 and max in 99 rt? We can't do both in 99 comparisons rt?
we can: suppose the input is in increasing order,then the following code will only take 99 comparisons.


for (i=1;i<100;i++)

if (a[i]>=max)

i.e here ,the code will never execute the else part becuz the i/p is in increasing order(non-decreasing order).
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)
i thought by min, it meant best case.
like in binary search,
minimum no. of comparisons to find the element is 1.
No. That is the best case. But if question is asked like this, it always means the worst input.
ok.. thanks :)
When n is odd what is the number of comparisons?

@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

Why in the recurrence relation have you added 2 , why not some constant c ?
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..
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.
can any one please solve the recurrance. not able to find 3/2n-2
Hi. It is the average case. Therefore it's 1.5n-2

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

@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.
@Hcas Hgnis

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

So, the average number of comparisons will be  







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

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

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

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



thanks @vizzard110

+37 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]

by Active (4.8k points)
+21 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$   



by Loyal (5.6k points)
edited by
what if we have total numbers in odd

The most complete explanation of Tournament method. Thanks.

This is a great underrated answer.

best answer thanks @Rishav Kumar Singh

2 ^-logn is 1/n ? how you reduced. i cant understand
+11 votes

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


   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)
please explain how u solve this recurrence relation
+7 votes
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
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.1k points)
+5 votes
by Active (1.2k points)
+5 votes

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 (1.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,167 answers
94,017 users