5
$\begingroup$

Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a recurrence of:

$$\begin{align*} T(n) & \leq T(n/3) + T(2n/3) + O(n)\\ & = O(n \log n) \end{align*}$$

However, this assumes that there exists an input which would always split the recurrence in the worst possible case. I am not convinced that this input always exists.

Question: Is there a general procedure to create a worst-case input for the median-of-medians algorithm with $k=3$ for an input of any length $n$?

If it helps, you can assume $n$ is of some particular format and that we are always searching for the exact median (as opposed to querying the $i$-th order statistic). You can also assume that the algorithm groups elements deterministically (e.g. incrementally group 3 elements).


You can choose any deterministic implementation if it helps, here is one for reference. Given an input array $A$ of $n$ distinct elements and query $i$ for the $i$-th order statistic, the $\mathrm{SELECT}(A, i)$ procedure is as follows:

  1. Divide $A$ into $\lfloor \tfrac{n}{3} \rfloor$ groups of length $3$.
    • We can do this by putting $\{a_1, a_2, a_3\}$ as group $G_1$, then $\{a_4, a_5, a_6\}$ as group $G_2$, and so on...
    • If $n \neq 3k$ then we can create one more group with the remaining 1 or 2 elements.
  2. Find the median of each group $G_i$ and store them in a list $M$.
    • We can do this by creating $M = [\mathrm{med}(G_1), \mathrm{med}(G_2), \ldots ]$.
  3. Recursively call this function to get the median of medians $x = \mathrm{SELECT}(M, \lfloor \tfrac{n}{6}\rfloor)$.
  4. Partition $A$ about $x$ into $A_1$ and $A_2$.
    • Let all elements in $A_1$ be less than $x$. (Assume order is retained)
    • Let all elements in $A_2$ be greater than $x$. (Assume order is retained)
  5. If $i = |A_1| + 1$ return $x$
  6. If $i < |A_1| + 1$ return $\mathrm{SELECT}(A_1, i)$.
  7. If $i > |A_1| + 1$ return $\mathrm{SELECT}(A_2, i - |A_1| - 1)$.

The biggest issue I am having for constructing a worst case input, is that we need $A$, $M$, and $A_1$ or $A_2$ to exhibit worst-case behavior. Since $M$ is nested in $A$ and $A_1$ or $A_2$ are subsets of $A$, getting all of this coordinated is very difficult.


Additional Notes:

We can always show that the initial recurrence will split into a problem of size $n/3$ and $2n/3$, perhaps we can also do this for the next level down, however I doubt it can be done consistently for levels below. This is relevant and important, because if you can show that our second recurrence will in fact be on something less than $2n/3$, then we have a linear time algorithm! This is because we'd get a recurrence:

$$T(n) \leq T(n/3) + T(\alpha n) + O(n)$$

Where $\alpha < 2/3$ thus, by the uneven split theorem this must be linear a la $T(n) = O(n)$.

$\endgroup$
  • $\begingroup$ The answer could depend on the exact way that the algorithm is implemented. For example, under some implementations, it seems that $1,\ldots,n$ might be a bad input. $\endgroup$ – Yuval Filmus Apr 2 at 14:26
  • $\begingroup$ @YuvalFilmus any deterministic implementation is fine if you can find a worst case input for it. I'll write up a sample implementation just for reference. $\endgroup$ – ryan Apr 2 at 16:14
  • $\begingroup$ @YuvalFilmus I updated a sample implementation. For example, with this standard implementation $\{1, 2, \ldots n\}$ would be a very good input, because the median of medians would basically split the array in half regardless of where the query is located. This would actually give a recurrence of roughly $T(n) = T(n/3) + T(n/2) + n = O(n)$. $\endgroup$ – ryan Apr 2 at 16:37
3
+50
$\begingroup$

Whether or not the median-of-medians algorithm with groups of size 3 runs in linear time is an open problem as said in [1] (while they proposed a variant running in linear time). I checked some follow-up papers and no one has a progress on showing the complexity of this algorithm. I believe it still remains open now.


[1] Chen, K., & Dumitrescu, A. (2015, August). Select with groups of 3 or 4. In Workshop on Algorithms and Data Structures (pp. 189-199). Springer, Cham.

$\endgroup$
  • $\begingroup$ That is a paper I came across a while ago, but for some reason could not find it when I went looking (before I wrote up this question). Thank you for linking it! I believe they show an alternate method where $k-3$ is worst-case linear time, but not the standard median-of-medians method (yes just what you said :). I will look into this. I'll leave the question open for the time being in case someone miraculously can answer this. $\endgroup$ – ryan Apr 13 at 4:22

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.