(a) Modify the procedure in Example 10.48 as follows: For any S ⊂ R, where |S| = n, partition S as S1 ∪ S2, where |S1| = |S2|, for n even, and |S1| = 1 + |S2|, for w odd. Show that if f(n) counts the number of comparisons needed (in this procedure) to find the maximum and minimum elements of S, then f is a monotone increasing function.
(b) What is the appropriate "big-Oh" form for the function f of part (a)?