The selection algorithm (to find the kth smallest value in a list), described in the class (and in the book), uses columns of size 5. Assume you implement the same selection algorithm using columns of size 7, rather than 5. (a) Exactly how far from either end of the array is the median of medians guaranteed to be. Just give the high order term. (Recall that with columns of size 5 we got 3n/10 .)

(b) Write down the recurrence for a Selection algorithm based on columns with 7 elements each, using (the full) bubble sort to find the median of each column. (You can ignore floors and ceilings, as we did in class.) You do not have to give the algorithm, but state where each of the terms in your recurrence comes from. (For example, you might say that the n 1 term comes from partition.)

(c) Solve the recurrence, and give the high order term exactly.

(d) How does this value compare with what we got in class for columns of size 5?