A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
From MaRDI portal
Publication:3936210
DOI10.1137/0211022zbMath0478.68061MaRDI QIDQ3936210
Allan Borodin, Stephen A. Cook
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211022
Related Items
Trade-offs between communication throughput and parallel time, Graph properties checkable in linear time in the number of vertices, Time-space tradeoffs for algebraic problems on general sequential machines, Oracle branching programs and Logspace versus \(P^*\), Lower bounds on the length of universal traversal sequences, Trade-offs between communication and space, The computational complexity of universal hashing, Time-space tradeoffs for set operations, Time-space tradeoffs for branching programs, Determinism versus nondeterminism for linear time RAMs with memory restrictions, Time-space tradeoffs in algebraic complexity theory, On lower bounds for read-\(k\)-times branching programs, Efficient simulation of synchronous systems by multi-speed systems, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?
