Tight lower bounds for selection in randomly ordered streams
Amit Chakrabarti, T. S. Jayram, Mihai Pǎtraşcu · 2008
We show that any algorithm computing the median of a stream presented in random order, using polylog(n) space, requires an optimal Ω(log log n) passes, resolving an open question from the seminal paper on streaming by Munro and Paterson, from FOCS 1978. 1