Now, recall median-of-medians algorithm to solve selection problem. Complete following exercises.

1. To guarantee O(n) time, the median-of-medians algorithm makes recursive calls only when the input size n ≥ 80; however, the choice of this constant 80 is somewhat arbitrary. In fact, we can still achieve O(n) time even if we make recursive calls on smaller input. What is the smallest input size with which we can make a recursive call, while maintaining O(n) time? Carefully justify your answer.

2. The median-of-medians algorithm partitions the input into groups of 5 elements, but it also works if we partition the input into groups of 7. Prove carefully that this modified algorithm still runs in O(n) time.