Gate @Zeal

Question

Let $'n'$ is an odd number and

 

1. $X$ be the minimum number of comparisons required to find the minimum and the maximum of 'n' numbers

 

2. $Y$ be the minimum number of comparisons required to find the minimum and the maximum of 'n+1' numbers.

 

Then which of the following statement is $True$ ?

 

$a) \ X + Y = 3(n-1) + 1$

$b) \ | X - Y | = 3n $

$c) \ | X - Y | = 1 $

$d)$ $X = \left ( \frac{3(n-1)}{2} + 1 \right )$ and $Y = \left ( \frac{3(n-2)}{2} + 1 \right )$

Answer 1

In this question we are given that n is an odd number now

let's analyse the tournament method which gives same no of comparisons as the CLRS method or the DAC approach

 

We have n elements in our array.Lets suppose this n is even.

So we compare pair of adjacent elements and but them in two separate bags.Lets call these bags as loser bag and winner bag.The one which wins the comparison goes to the winner bag while the other goes to the loser bag.Since we have n elements and n is even so we have exactly n/2 pairs of adjacent elements and for each pair we need only one comparison to determine who is winner and who is loser.

 

So far we have n/2 *1=n/2 comparisons.

 

Now we have the two bags,one filled with the losers and one with the winners.Each bag will have exactly n/2 elements as n is even and finding the max among winners will take exactly n/2-1comparisions while finding the min among the losers will take another n/2-1 comparisons

Total we have n/2+n/2-1+n/2-1

=3n/2-2

Now what if n is an odd number

we can simply ignore the last number of the array and use the rest n-1 numbers which are there as they are even

So with n-1 numbers finding min and Max will take (n-1)/2+{(n-1)/2-1}+{(n-1)/2-1} comparisons which is same as 3(n-1)/2-2

 

Now the ignored element can lie in three positions

i) above max and obviously above min

ii) between max and min

iii)below min and obviously below max

 

For case i) we will get 1 more comparison and for the rest we will get 2

so let's go by the worst case which gives the total no of comparisons as

 

3(n-1)/2-2+2= 3(n-1)/2

 

Part 1 of the question is asking about this one

Part 2 is saying 'n+1' is even so we need to take the case of 'n' is even and replace the 'n' by 'n+1',which is 3(n+1)/2-2

X+Y=3(n-2)=3(n-1)+1 option a.

|X-Y| =|-3+2|=1 option c.