Groups Of Three

Median of medians picks its pivot by splitting the input into groups of 5, taking each group's median, and recursing to find the median of those medians. The 6.046 analysis shows at least $3(\lceil n/10 \rceil - 2)$ elements fall on each side of that pivot, which yields

$T(n) = T!\left(\frac{n}{5}\right) + T!\left(\frac{7n}{10} + 6\right) + \Theta(n)$

and this solves to $\Theta(n)$ . A student proposes groups of 3 instead, since sorting a group of 3 is cheaper. What does that change?

The algorithm becomes incorrect: the pivot is no longer guaranteed to have the claimed rank, so the wrong element can be returned

The two subproblem sizes become about $n/3$ and $2n/3$ , which sum to exactly $n$ , so the recursion becomes $\Theta(n \log n)$

It stays $\Theta(n)$ with a smaller constant, because sorting groups of 3 costs less per group

It stays $\Theta(n)$ , because $1/3$ and $2/3$ are each strictly less than 1