First time here? Checkout the FAQ!
+18 votes
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________
asked in Algorithms by Veteran (87.3k points)   | 4.4k 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.

5 Answers

+28 votes
Best answer

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/2n -2 

 Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -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 .....

answered by Active (1.2k points)  
selected by
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

+11 votes

Another easier way to find it is by using Tournament Method Technique -

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

2. To find the largest element - 

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

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

answered by Loyal (2.7k points)  

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

How it is, please explain?? 

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



answered by (405 points)  
please explain how u solve this recurrence relation
+5 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]



answered by Loyal (3.4k points)  
0 votes
answered by (101 points)  

Related questions

Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2416 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,115 questions
33,691 answers
31,098 users