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

Dark Mode

106 votes

Best answer

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 -

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

0

@Tmajestical No. They didn’t say that array is sorted. Hence, we need to give generalized answer which is achieved only through Tournament Method. We can’t assume sorted array here.

0

edited
Oct 13
by Tmajestical

@Abhrajyoti00, I agree with you, they have not specified that the array is sorted. But they were asking for minimum number of comparisons, which means best case, and best case of max-min will occur when array is sorted. Which is why I have considered a sorted array. 3n/2 -2 is fine, but it would be the average case of the standard max min algorithm or for an optimized version, it may be the worst case (upper bound).

0

70 votes

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)) + 2T(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 ..... **

@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

2

52 votes

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

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$

0

43 votes

**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]**