in Algorithms edited by
53,438 views
89 votes
89 votes
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
in Algorithms edited by
53.4k views

4 Comments

Tournament method is used.

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

Here you go

what kushagra is saying

13
13

16 Answers

12 votes
12 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

1 comment

please explain how u solve this recurrence relation
1
1
8 votes
8 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
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.
7 votes
7 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

5 votes
5 votes
Answer:

Related questions