Comparison-based time-space lower bounds for selection

Research output: Contribution to journalArticlepeer-review

Abstract

We establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω(nlog logS 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 log n, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman [1996], and also complements recent lower bounds that are restricted to sequential access, as in the multipass streaming model [Chakrabarti et al. 2008b]. We also prove that any comparison-based, deterministic, multipass streaming algorithm for finding the median requires Ω(n log*(n/s)+ nlog s n) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s log2 n. We get deterministic lower bounds for I/O-efficient algorithms as well. The proofs in this article are self-contained and do not rely on communication complexity techniques.

Original languageEnglish (US)
Article number26
JournalACM Transactions on Algorithms
Volume6
Issue number2
DOIs
StatePublished - Mar 1 2010
Externally publishedYes

Keywords

  • Adversary arguments
  • Lower bounds
  • Median finding
  • RAM
  • Randomized algorithms
  • Streaming algorithms
  • Time-space trade-offs

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Comparison-based time-space lower bounds for selection'. Together they form a unique fingerprint.

Cite this