12k views
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
edited | 12k views
0
seeing the question directly how can one say that which algorithm will give us minimum comparisons?
+1

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.

+2
0
148

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.$

answered by Active (4.2k points)
selected by
+2

After the first round of Tournament , there will be exactly n/2 numbers = 50 that will loose the round

How it is, please explain??

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

answered by Active (1.1k points)
edited by
0
If we do not consider divide n conquer:
and the keys are in sorted order, then we can find the min and max in 99 comparisons.Even the iitkgp solutions said that answer is 148 but i dont know why they havent considered the ''99 comparison'' case which is minimum.
0
Min in 99 and max in 99 rt? We can't do both in 99 comparisons rt?
0
we can: suppose the input is in increasing order,then the following code will only take 99 comparisons.

min=max=a[0];
for (i=1;i<100;i++)
{

if (a[i]>=max)
max=a[i];
else
min=a[i];

}
i.e here ,the code will never execute the else part becuz the i/p is in increasing order(non-decreasing order).
+2
We cannot assume a special case for input (it should work for all inputs)

(i.e., we have to find the min. number of comparisons in the worst case)
+1
i thought by min, it meant best case.
like in binary search,
minimum no. of comparisons to find the element is 1.
+4
No. That is the best case. But if question is asked like this, it always means the worst input.
+1
ok.. thanks :)
0
When n is odd what is the number of comparisons?
+2

@arjun sir ,

how you formed below equations

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

0
Why in the recurrence relation have you added 2 , why not some constant c ?
+7
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..
0
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.
+1
can any one please solve the recurrance. not able to find 3/2n-2
+1
Hi. It is the average case. Therefore it's 1.5n-2
+1

@Arjun sir would you please tell me how we are getting 3/2n-2  from recurrence equation

0
@arjun Can we use extra O(logn) memory here?If yes then the answer should be n + ceil(logn) - 2 considering we keep track of the nodes that lose to the smallest element which will be at max logn.
0
@Hcas Hgnis

The maximum number of comparisons in your code will be  (2n-2).

So, the average number of comparisons will be

[(n-1)+(2n-2)]/2

(3n-3)/2

1.5(n-1)

1.5(99)

149

Can we solve this like that?
0
If number are already sorted then why do we even need comparison.We can directly say first element is min while last is max?

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]

answered by Active (5.1k points)

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

answered by (411 points)
+1
please explain how u solve this recurrence relation

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$

answered by Loyal (5.4k points)
edited
0
what if we have total numbers in odd
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.
answered by Active (2.3k points)
answered by Active (1.5k points)
+1 vote

Consider n=8 elements in an array {1,4,5,8,3,2,7,9}
Lets make a tournament bracket for them, where at each stage the winner is the minimum element between the two.

As you can see, number of comparisons being done = n-1 = 7

Similarly, to find the maximum element you again will need n-1 comparisons!
So total no of comparisons to find min and max=2(n-1)
Hmm...there is one optimisation to it !!

The last level in the tree is making n/2 comparisons(4 in this case) and these are being repeated while finding the minimum and maximum!

So doing the last level comparisons only once, we do n/2 comparisons less
Hence 2(n-1) - n/2 = 2n-2-n/2 = 3n/2-2.

So, here n= 100

Using 3n/2-2 = 150-2 = 148

answered by Active (1.4k points)
(3n/2) - 2

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

3(n-1)/2

For odd
answered by (187 points)
3n/2-2 then 3*100/2-2=150-2=148
answered by (381 points)

1
2