Recall that the median-of-medians algorithm divides the input into groups of 5 (or 7) elements, finds their medians, and recursively selects the median of those medians to use as a pivot.

Derive the recurrence relation for the worst-case running time when using groups of 7, accounting for the recursive calls on the groups and the final selection step.

Prove that the recurrence relation solves to O(n) by showing that the work done outside the recursive calls is linear and the recursive calls shrink the problem size by a constant factor.