A time-space tradeoff for sorting on non-oblivious machines
- 1 October 1979
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 22 (02725428) , 319-327
- https://doi.org/10.1109/sfcs.1979.4
Abstract
A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.Keywords
This publication has 12 references indexed in Scilit:
- Upper and lower bounds on time-space tradeoffsPublished by Association for Computing Machinery (ACM) ,1979
- Improved bounds on the problem of time-space trade-off in the pebble gamePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Space-time trade-offs on the FFT algorithmIEEE Transactions on Information Theory, 1978
- A Time-Space Trade-OffJournal of the ACM, 1978
- Time-space tradeoffs for computing functions, using connectivity properties of their circuitsPublished by Association for Computing Machinery (ACM) ,1978
- Saving space in fast string-matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Time-space trade-offs in a pebble gamePublished by Springer Nature ,1977
- Time bounds for selectionJournal of Computer and System Sciences, 1973
- On the Optimality of Some Set AlgorithmsJournal of the ACM, 1972
- The recognition problem for the set of perfect squaresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1966