Finding the Median (Obliviously) with Bounded Space

Paul Beame, Vincent Liew, Mihai Pǎtraşcu

We prove that any oblivious algorithm using space $S$ to find the median of a list of $n$ integers from $\{1,...,2n\}$ requires time $\Omega (n\log {\log }_{S}n)$. This bound also applies to…