Median-of-medians in O(log n) memory

Question

Is there a way to use median-of-medians to find a median in,
simultaneously, ​ ​O(log n) ​ ​memory and O(n) comparisons?

The user orlp on this site seems to claim that there is.

Getting ​ ​O(log n) ​ ​auxiliary memory seems to be straightforward,
but I have no clue how that can be improved to O(log n) memory.

Answer 1

There is no such way.


This paper shows

that any comparison-based randomized algorithm for finding the
median requires $\Omega(n \log \log_{\hspace{.02 in}S} n)$ expected time in the RAM model
(or more generally in the comparison branching program model),
if we have S bits of extra space besides the read-only input array.
This bound is tight for all $S\gg \log n$, and remains
true even if the array is given in a random order.

$n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)} \; = \; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$
and
$\operatorname{polylog}(n) = 2^{\log(\hspace{.02 in}\operatorname{polylog}(n))} = 2^{O(\hspace{.02 in}\log(\hspace{.02 in}\log(n)))} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}o(1)}\hspace{-0.03 in}\right)} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$


so since


$2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \: \cdot \: \operatorname{polylog}(n) \;\;\; \subseteq \;\;\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \: \cdot \: 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$
$= \;\;\; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}+\hspace{.02 in}(\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)} \;\;\; = \;\;\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$

and

$\Omega \hspace{-0.04 in}\left(n\log \log_{2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}} n\right) \;\;\; = \;\;\; \Omega \hspace{-0.04 in}\left(n\cdot \left(\log(\hspace{.02 in}\log(n))-\log \left(\log \left(2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}\right)\right)\right)\right)$
$= \;\;\; \Omega(n\cdot ((1\cdot \log(\hspace{.02 in}\log(n)))-((1-\Omega(1)) \cdot \log(\hspace{.02 in}\log(n)))))$
$= \;\;\; \Omega(n\cdot (1-(1-\Omega(1))) \cdot \log(\hspace{.02 in}\log(n))) \;\;\; =$
$\Omega(n\cdot \Omega(1) \cdot \log(\hspace{.02 in}\log(n))) \;\;\; = \;\;\; \Omega(n \log \log n)$

and

pointers can be represented with ​ O(log(n)) ​ bits

,


even when one measures with polylog(n)-bit machine words and assumes that
input-elements fit into such words, comparison-based selection algorithms
that use at most ​ ​ ​ $2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$ ​ $\Big($equivalently, ​ $n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)}\Big)$ ​ ​ ​ space
require ​ $\Omega(n \log \log n)$ ​ comparisons on average,
even if the array is given in a random order.