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

Minimum no of comparisions =148

Comments

this is using devide and conquer .Actually we can do better than this using straight min-max algo  and minimum number of comparisons will be n-1 =100-1=99 comparisons.Actually in this question nothing is said about so i think 99 is better in this case but looking at the options we can justify that this question has asked using devide and conquer min-max algo.What when options will not be there?

---

I think we can find either max or min using 99 comparisions but not both at same time. If you do ,this will eventually increase comparison.

---

What is this formula for ????

---

@paraskk if we want to find both minimum and max then we use this formula. if the total no is even then this formula is used

https://gateoverflow.in/1917/gate2014-1-39 

https://gateoverflow.in/1248/gate2007-50

Answer 2

(3n/2) - 2

Direct formula for finding max and min element in even n.

 

3(n-1)/2

For odd

Answer 3

3n/2-2 then 3*100/2-2=150-2=148

Answer 4

Simple and brute force approach : 

Since, we have 100 elements and initially min=max=0, first two elements are chosen and compare them and update the value of min and max. So, 1 comparison here.

For the next 2 elements, we’ve to compare them first, then the minimum value from them is compared to min, similarly the maximum value from them is compared to max. Therefore, 3 comparisons are required.

Similarly, for the next 2 elements, 3 comparisons are required.

We can observe a pattern here like

2 elements → 3 comparisons

4 elements → 6 comparisons

.

.

.

98 elements → 98*(3/2) = 147 comparisons

(98 here because first two elements are compared once, and we started comparing 3 times from the third element. So, 3^rd and 4^th element constitute 2 elements, similarly, 3^rd,4^th,5^th and 6^th constitute 4 elements and so on.)

Therefore, total number of comparisons  = 147 + 1 = 148 

(1 is added because first two elements are compared once at beginning)