In the max and min finding algorithms, we need n-1 comparisons. According to our textbook, however, at most 3*n/2 comparisons suffice to find both the minimum and maximum.

Basic Strategy: Maintain the minimum and maximum of elements seen so far. Dont compare each element to the minimum and maximum separately. Process elements in pairs. Compare the elements of a pair to each other. Then compare the larger element to the maximum so far, and compare the smaller element to the minimum so far. This leads to only 3 comparisons for every 2 elements.

Setting up the initial values for the min and max depends on whether n is odd or even. If n is even, compare the first two elements and assign the larger to max and the smaller to min. Then process the rest of the elements in pairs. If n is odd, set both min and max to the first element. Then process the rest of the elements in pairs.

a) Write the above description in algorithmic form. Follow this notation:

b) Show that your algorithm need at most 3*n/2

MINIMUM(A) 1 minA1 2 for 2 to A.length 3 ?f min > A[i] 4 5 return min min- A