A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
From MaRDI portal
Publication:3936210
DOI10.1137/0211022zbMath0478.68061OpenAlexW1976463987MaRDI 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
Time-space trade-offs for triangulations and Voronoi diagrams ⋮ A simple proof of a time-space trade-off for sorting with linear comparisons ⋮ On lower bounds for read-\(k\)-times branching programs ⋮ Strictly in-place algorithms for permuting and inverting permutations ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Time-Space Trade-offs for Triangulations and Voronoi Diagrams ⋮ Two time-space tradeoffs for element distinctness ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Branching Programs for Tree Evaluation ⋮ Upper bounds for time-space trade-offs in sorting and selection ⋮ On the time and space complexity of computation using write-once memory or is pen really much worse than pencil? ⋮ Meanders and their applications in lower bounds arguments ⋮ On time versus space III ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Sorting and ranking of self-delimiting numbers with applications to tree isomorphism ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Incremental branching programs ⋮ Time-space tradeoffs for algebraic problems on general sequential machines ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Oracle branching programs and Logspace versus \(P^*\) ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Bi-criteria optimization of decision trees with applications to data analysis ⋮ Lower bounds on the length of universal traversal sequences ⋮ Trade-offs between communication and space ⋮ Efficient simulation of synchronous systems by multi-speed systems ⋮ The computational complexity of universal hashing ⋮ Time-space tradeoffs for set operations ⋮ Trade-offs between communication throughput and parallel time ⋮ Choice-memory tradeoff in allocations ⋮ Approximation in (Poly-) logarithmic space ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ A general class of resource tradeoffs ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Finding median in read-only memory on integer input ⋮ On oblivious branching programs of linear length ⋮ Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer ⋮ Time-space tradeoffs for branching programs ⋮ Determinism versus nondeterminism for linear time RAMs with memory restrictions
