GATE CSE
First time here? Checkout the FAQ!
x
+18 votes
4.4k views
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

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

 

 

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)  
Answer:

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
79,846 comments
31,098 users