Min and Max
Suppose we wish to find both the minimum and maximum values in an array of n distinct elements.
To individually find either the minimum or maximum, there is clearly a n-1 lower bound on comparisons, since we must compare every element at least once. We can save a comparison by first scanning for the minimum, removing it, then scanning for the maximum. This takes a total of 2n-3 comparisons.
Based on this observation, prove the following statement true or false:
“It takes at least 2n-c comparisons, for some constant c , to find both the minimum and the maximum in an array of n distinct elements.”