Problem 1

In class we considered the Select algorithm, which determines the ith smallest element in an array of size n in O(n) time for the worst case input. The first step of this algorithm is division into n/5 groups of 5 elements each.  Consider other two versions of this algorithm:  the first one uses division into n/3 groups of 3 elements each and the second one uses division into n/7 groups of 7 elements each. Otherwise both algorithms implement the same routine as Select. Which algorithm is asymptotically faster, the one with division into groups of 3, groups of 5 (standard Select), or groups of 7? Prove your statement.

Problem 2

We will say that the pivot provides x|n − x separation if x elements in the array are smaller than the pivot, and n − x elements are larger than the pivot. Suppose Bob knows a secret way to find a good pivot with  |  separation in constant time. But at the same time Alice knows her own secret technique, which provides separation  | , her technique also works in constant time. Alice and Bob applied their secret techniques as subroutines for the QuickSort algorithm.  Whose algorithm works asymptotically faster? Prove your statement.