9.1-2

9.1-2 Prove the lower bound of $3\lceil n/2 \rceil - 2$ comparisons in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)

We need to analyze even and odd case separately.

n is Even: If n is even we will divide the numbers in to n/2 pairs and compare elements in pairs and keep the small elements in array and larger elements in another array(you can swap with in the array as well if changing the input is allowed). To compare n/2 with n/2 elements we need n/2 comparisons. We now have Small array and large array. The smallest element must be in smallest array and largest element must be in the largest array. We use MINIMUM(A) to find smallest element on small array similarly we can MAXIMUM(A) to find the largest on large array. This will take n/2 - 1 for MINIMUM and MAXIMUM operations. since n is even n/2 = $\lceil n/2 \rceil$ We can now add up all comparisons $$\lceil n/2\rceil+\lceil n/2\rceil-1+\lceil n/2\rceil-1$$ $$3\lceil n/2\rceil-2$$ n is odd: If n is odd assign maximum and minimum to the first element and divide the array in to (n-1)/2 pairs. Let compare elements in pairs and keep the small elements in array and larger elements in another array. To compare (n-1)/2 pairs of elements we need (n-1)/2 comparisons. we now have a small array with small numbers and large array with large numbers. The smallest element must in small array and similarly large element must be in large array. We can use MINIMUM(A) to find a smallest element on small array and MAXIMUM(A) on large array to find the largest element.This needs (n-1)/2 -1 for both arrays. Later we need to compare the first element which we assigned as maximum and minimum element with smallest and largest element to find smallest and largest element. It will take two comparisons. since n is even (n-1)/2 = $\lceil (n-1)/2 \rceil$ We can now add up all comparisons $$\lceil (n-1)/2\rceil+\lceil (n-1)/2\rceil-1+\lceil (n-1)/2\rceil-1+2$$ $$3\lceil (n-1)/2\rceil$$ $$3\lceil n/2 \rceil-3/2$$ since 2 > 3/2 .The no of comparisons are more when n is even. The worst case occurs when n is even.