A time-space tradeoff for sorting on non-oblivious machines

DOI10.1016/0022-0000(81)90037-4zbMath0462.68011OpenAlexW2052404100MaRDI QIDQ1152950

Allan Borodin, Martin Tompa, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90037-4

zbMATH Keywords

model of computationnon-oblivious programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Algorithms in computer science (68W99)

Related Items (21)

Strictly in-place algorithms for permuting and inverting permutations ⋮ Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ Two time-space tradeoffs for element distinctness ⋮ A note on the decoding complexity of error-correcting codes ⋮ Upper bounds for time-space trade-offs in sorting and selection ⋮ A lower bound for read-once-only branching programs ⋮ Constant work-space algorithms for facility location problems ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Time-space tradeoffs for algebraic problems on general sequential machines ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ A time-space tradeoff for language recognition ⋮ Trade-offs between communication and space ⋮ The computational complexity of universal hashing ⋮ Time-space tradeoffs for set operations ⋮ Approximation in (Poly-) logarithmic space ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Determinism versus nondeterminism for linear time RAMs with memory restrictions

Cites Work

• Unnamed Item
• Unnamed Item
• On the time-space tradeoff for sorting with linear queries
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Time-space trade-offs in a pebble game
• A note on time-space tradeoffs for computing continuous functions
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Space-time trade-offs on the FFT algorithm
• A Time-Space Trade-Off
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• On the Optimality of Some Set Algorithms

This page was built for publication: A time-space tradeoff for sorting on non-oblivious machines