$2\cdot n - 2 $ comparisons are sufficient but not necessary.
We can find both maximum & minimum in using less than $2\cdot n - 2 $ comparisons.
Superficially, if you are doing (n - 1) comparisons to find maximum of n elements, then minimum can be found by comparing between those numbers who lost in their first comparison.
Here is an interesting excerpt from Cormen's book that might be useful:
Simultaneous Minimum & Maximum
|
"It is not difficult to devise an algorithm that can find both the minimum and the maximum of n elements using $\Theta(n)$ comparisons, which is asymptotically optimal.Simply find the minimum and maximum independently, using n − 1 comparisons for each, for a total of 2n − 2 comparisons.
In fact, at most 3 * Floor(n/2) comparisons are sufficient to find both the minimum and the maximum. The strategy is to maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, at a cost of 2 comparisons per element,we process elements in pairs. We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd or even. If n is odd, we set both the minimum and maximum to the value of the first element, and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison on the first 2 elements to determine
the initial values of the minimum and maximum, and then process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3*Floor(n/2) comparisons. If n is even, we perform 1 initial comparison followed by 3(n − 2)/2 comparisons, for a total of 3n/2 − 2. Thus, in either case, the total number of comparisons is at most 3 *Floor(n/2)."
- Introduction to Algorithms(CLRS), 3rd Edition,Page No 184 - 185
|
On removing the floor function it can be observed that
1. If n is even, $3 \cdot \frac{n}{2} - 2$ comparisons will be required.
2. If n is odd, $3 \cdot \frac{n}{2} - 1.5$ comparisons will be required.
So I guess Option C will be the correct answer.
$3 \cdot \frac{n}{2} - 1$ comparisons will be sufficient without odd, even concern, for finding both maximum & minimum out of n numbers.
