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