Consider a generalization of Median-of-Five algorithm which has a parameter for an integer 1. Instead of partitioning input into n/5 blocks of size 5, the algorithm partitions the input into n/(2 + 1) blocks of size 2 + 1 (assume n is a power of 2 + 1). Note that the algorithm becomes the median-of-five algorithm when = 2.

a) Follow the same steps as slide 14 of lecture notes to derive a recursive formula for the time complexity T(n) of this algorithm as a function of n and (there is no need to solve the recursion; just deduce the recursive definition of T(n)).

b) Assume = 3 (the algorithm will be median of 7). Rewrite the recursion for this particular and try to solve the recursion by guessing that T(n) O(n). Follow the same steps as in the slides and indicate whether we can state T(n) O(n).

c) [bonus] Assume = 1 (the algorithm will be median of 3). Rewrite the recursion for this particular and solve the recursion to provide a tight bound (in terms of ) for the time complexity of this algorithm.