A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
Authors:
- A. BorodinABA. Borodin
- S. CookSCS. Cook
- 1 May 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (2) , 287-297
Abstract
In a general sequential model of computation, no restrictions are placed on the way in which the computation may proceed, except that parallel operations are not allowed. We show that in such an unrestricted environment ${\text{TIME}} \cdot {\text{SPACE}} = \Omega (N^2 /\log N)$ in order to sort N integers, each in the range $[1,N^2 ]$.
Keywords
This publication has 8 references indexed in Scilit:
- Hardware complexity and parallel computation1980
- On uniform circuit complexity1979
- On simultaneous resource bounds1979
- A time-space tradeoff for sorting on non-oblivious machines1979
- Shifting Graphs and Their ApplicationsJournal of the ACM, 1976
- Boolean matrix multiplication and transitive closure1971
- The recognition problem for the set of perfect squares7th Annual Symposium on Switching and Automata Theory (swat 1966), 1966
- Crossing sequences and off-line turing machine computations1965