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

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