5.2k views
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________
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.

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

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.

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

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.

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

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]

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

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