GATE CSE 2014 | Set 1 | Question: 39

Question

The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________

Comments

https://chatgpt.com/share/6942b4af-b9c4-8002-8687-06009ff4144f

---

.                                                                                         With Divide and Conquerors  (3n/2  -  2)

Minimum number of  Avg. comparision to find MIN/MAX:

                                                                                          Without Divide and Conqueror (3n/2 - 1)

Best is with D&C.

 

---

By first comparing elements in pairs --> then comparing the smaller to min and larger to max so that we reduce comparisons.

Answer 1

NOTE: At level 1 in $\frac{n}{2}$ comparisons we are finding Both MINIMUM as well as MAXIMUM for level 2.  

Let's see for minimum,

At level 1 :$\frac{n}{2}$ comparisons

At level 2 : $\frac{n}{2^2}$ comparisons

At level 3 : $\frac{n}{2^3}$ comparisons

so on.... 

At level logn : $\frac{n}{2^{logn}}$ comparisons

So, Total number of comparisons will be 

$\frac{n}{2}$ +  $\frac{n}{2^2}$ +  $\frac{n}{2^3}$ + .....+ $\frac{n}{2^{logn}}$

$\Rightarrow$ n ($\frac{1}{2}$ +  $\frac{1}{2^2}$ +  $\frac{1}{2^3}$ + .....+ $\frac{1}{2^{logn}}$ )   [apply Sum of G.P]

$\Rightarrow$ $n\frac{1}{2}(\frac{1-(\frac{1}{2})^{logn}}{1-\frac{1}{2}})$

$\Rightarrow$ $n\frac{1}{2}(\frac{1-(2)^{-logn}}{\frac{1}{2}})$

$\Rightarrow$  $n(1-\frac{1}{n})$

$\Rightarrow$  $n-1$

So,total comparisons required to find minimum of n element is n-1 comparisons.

similarly for Max n-1 comparisons required.

So total comparisons for both min and max will be

$2(n-1) - \frac{n}{2}$     $\Rightarrow$ $\frac{3n}{2}-2$   

 [ $\frac{n}{2}$ is reduced because at Level 1 we have taken $\frac{n}{2}$ for both while min and max calculation ]

coming to question n = 100,

total comparisons $\Rightarrow$ $\frac{3 * 100}{2}-2 =  148$   

 

 

Comments

Indeed best answer.

---

I don't know the selection precedure of best answer. This answer should be the best @Arjun

---

@Rishav Kumar Singh does this formula works for both even and odd values of n?

 

Answer 2

We can solve this question by using Tournament Method Technique -

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

2. To find the largest element - 

1. After the first round of Tournament , there will be exactly $n/2$ numbers $= 50$ that will loose the round.
2. 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.$

Comments

@Pranavpurkar For Max and 2^nd Max element in worst case:- 

Using Tournament Method

To find Max → $n-1$ comparisons are required.

Now while solving for the max, in each level we get one candidate for 2^nd max (remember the 2^nd max element will be compared only once with the max element). Since height of the binary tree is logn, hence we have total $\lceil logn \rceil$ candidates for 2^nd max. To find the 2^nd max element, we require, $\lceil logn \rceil -1$ comparisons.

Therefore overall to find max and 2^nd max in worst case no. of comparisons required

= $n+\lceil logn \rceil -2$ 

(This formula is given in CLRS 3^rd edition, Ex -9.1-1 of pg 215)

---

@Tmajestical The question has asked for min comparisons to find the minimum and the maximum of $n$ elements. Here they didn’t mention best case input, or worst case input. Hence we must use the optimal algo which is the tournament method which gives the number of comparisons = $\lceil3n/2 -2 \rceil$ exactly in all cases.

---

@Abhrajyoti00, okay, thanks!

Answer 3

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

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

Comments

thanks @vizzard110

---

here it says the best case, not minimum so why not 199?

---

In best case it should be (n-1), your answer is correct

Answer 4

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]

Comments

thanks

---

what would be the approach for second min and max?

answer would be?

99+49(min)?

Answer 5

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

Comments

please explain how u solve this recurrence relation

Answer 6

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.