2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I believe some people call median of median the algorithm which selects an approximate median in linear time, and some people mean what you get when you combine that with quickselect, i.e. a linear-time algorithm to find the k'th element in an array (or in particular, find the median). Just two closely related things some people tend to call by the same name. $\endgroup$
    – Tassle
    Mar 14 at 22:18
  • $\begingroup$ @Tassle This is one of the algorithms where I haven't really been satisfied with when reading the first page of Google links. I felt something was confusing or missing in each of them. Is there a text book that this algorithm is in? It's not in CLRS unfortunately, and I don't have familiarity with other algorithms textbooks. $\endgroup$ Mar 14 at 23:52
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Note that the algorithm used to find the approximate median is sometimes what people refer to when they say "median-of-medians", hence the confusion experienced by the OP I think. $\endgroup$
    – Tassle
    Mar 14 at 22:20
  • $\begingroup$ Do you know of a textbook that describes the median of medians? I read all the articles on the first page of Google and more after googling "median of medians," and I just don't feel very satisfied with any of them, including the wikipedia article. The one on brilliant.org was probably the best one I read, but I still would prefer a textbook read for this algo. $\endgroup$ Mar 14 at 23:58
  • $\begingroup$ It’s described in CLRS and on Wikipedia, and probably in many other lecture notes and slides. $\endgroup$ Mar 15 at 0:00
  • $\begingroup$ Oh I didn't realize it was in CLRS. Found it in 9.3. Earlier I was doing a search for median of medians in the book and could not find it. $\endgroup$ Mar 15 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.