Specifically b, c, d.

3. (8 points) The linear-time "median-of medians" selection algorithm began by arbitrarily partitioning the elements into groups of size 5. (a) (2 points) If we change the group size of the deterministic linear time selection algorithm into groups of 3 , what is the running time of the algorithm? Next, you are going to figure what happen if we use groups of 4 (a normal exercise would have asked you to figure out what happen for groups of 7 ). Suppose we define the median of a group of 4 numbers to become the 2nd smallest number among the group. That is, the median of {3,9,102,514} is 9 . In general, we define the median of a group of 2t (even) numbers to become the t-th smallest number among the group. From now on, assume that we have applied the above definitions and use groups of size 4 to the algorithm. (b) (2 point) Show that if we are selecting the median k=n/2, after 3 levels of recursion the problem size becomes at most 45n/128. 1 (c) (2 point) Let us define two different function S(n) and T(n), where T(n) is the upper bound of runtime that solves the selection problem for an arbitrary rank k. We use S(n) to denote the upper bound of runtime that solves the selection for k=n/2 being exactly the median. Establish an upper bound of S(n) using T functions and n. (d) (2 point) Write down the recurrence relation of T(n) using both S(n) and T(n), then prove that both S(n)=O(n) and T(n)=O(n)