Comparison-based time-space lower bounds for selection
Author:
Open Access
- 1 March 2010
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 6 (2) , 1-16
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 Ω( n log log 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 > 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 )+ n log s n ) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s >log 2 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.Keywords
This publication has 23 references indexed in Scilit:
- Time-space trade-off lower bounds for randomized computation of decision problemsJournal of the ACM, 2003
- Selection from read-only memory and sorting with minimum data movementTheoretical Computer Science, 1996
- Average case selectionJournal of the ACM, 1989
- Upper bounds for time-space trade-offs in sorting and selectionJournal of Computer and System Sciences, 1987
- Applications of Ramsey's theorem to decision tree complexityJournal of the ACM, 1985
- A time-space tradeoff for sorting on non-oblivious machinesJournal of Computer and System Sciences, 1981
- Selection and sorting with limited storageTheoretical Computer Science, 1980
- Finding the medianJournal of Computer and System Sciences, 1976
- Expected time bounds for selectionCommunications of the ACM, 1975
- Time bounds for selectionJournal of Computer and System Sciences, 1973