Median of medians confusion -- the "approximate" median part

Question

I'm struggling with the median of medians algorithm, and I think it's perhaps more of a semantics thing rather than a technical thing. I've always thought the median of medians algorithm as finding an approximate median $p$ such that $p$ is within $20\%$ of the true median $M$ in the sorted array.

However, when I look at actual implementations, e.g., in https://brilliant.org/wiki/median-finding-algorithm/, the algorithm they posted returns an exact median, but at each level of the recursion, you may have some approximate median generated from a sublist of medians. And eventually you'll reach a level where the array is $\leq 5$ elements, ending the recursion. At this level, you obtain an exact median of the array you passed in. So I had thought all this time that this exact median computed at the last level is actually your estimate of the median in the original array passed in at the first level of the recursion.

So I had the same confusion as this poster https://stackoverflow.com/questions/52461306/something-i-dont-understand-about-median-of-medians-algorithm and some others.

Now that I understand this algorithm, I am now confused on how the median of medians actually finds an "approximate" median to the original array. In all the implementations I've seen, the median you find using median of medians is exact. So where does the approximate part come in other than approximating the median at each recursion level? Even Wikipedia describes as an algorithm that approximates a median. Yes, it approximates medians at various levels, but the final output is exact.

Or am I operating under a false premise in thinking that Median of Medians finds an approximate median to the ORIGINAL array?

Answer 1

Median-of-medians is a recursive algorithm which solves the more general selection problem: given an array $A$ of length $n$ (which we assume, for simplicity, has distinct elements) and an integer $k$, find the $k$'th smallest element (where $1 \leq k \leq n$). It works as follows:

• If $n \leq K$ (where $K$ is some constant), solve the problem by brute force.
• Otherwise, find an approximate median $x$ of $A$ in $O(n)$. By approximate median, we mean that $x$ is the $m$'th smallest element in $A$, where $\alpha n \leq m \leq (1-\alpha) n$ for some constant $\alpha < 1$.
• Use $x$ to split $A$ into elements smaller than $x$, comprising an array $A_{<x}$ of length $m-1$, and elements larger than $x$, comprising an array $A_{>x}$ of length $n-m$.
• If $m = k$, then output $x$. If $m > k$ then output the $k$'th smallest element of $A_{<x}$. If $m < k$ then output the $(k-m)$'th smallest element of $A_{>x}$.

The running time of the algorithm satisfies the recurrence $T(n) \leq T(\alpha n) + O(n)$, whose solution is $T(n) = O(n)$.

The algorithm finds the exact median, but it does so by repeatedly finding approximate medians.