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

Tournament method is used.

Ans = $1.5n-2 = 1.5*100 -2 = 150-2 = 148$

---

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.

---

Here you go

what kushagra is saying

Answer 1

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 2

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

@akshay7797 see this link I was also confused in solving this recurrence relation

https://math.stackexchange.com/questions/2829507/solve-the-recurrence-tn-2-tn-2-2

 

---

thanks @vizzard110

---

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

Answer 3

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

what if we have total numbers in odd

---

The most complete explanation of Tournament method. Thanks.

---

This is a great underrated answer.

---

best answer thanks @Rishav Kumar Singh

---

2 ^-logn is 1/n ? how you reduced. i cant understand

---

From the properties of logarithms

2^log n = n

Hence 2^-logn can be written as 2^log(n^-1) = n^-1 = 1/n

---

Indeed best answer.

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