What is the recurrence? Clearly, we compute the median of the n/5 medians. Then, what's the worst case for running select on what's left?
.
This is O(n) because (recursion tree).
.
(recursion tree).
