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

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

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

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

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]