A simple proof of a time-space trade-off for sorting with linear comparisons

DOI10.1016/0304-3975(86)90185-4MaRDI QIDQ1079376zbMATH OpenOpenAlexFDO

Authors Donald B. Johnson

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90185-4

zbMATH Keywords

linear branching programs

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the time-space tradeoff for sorting with linear queries
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A Time-Space Tradeoff for Element Distinctness
• Upper bounds for time-space trade-offs in sorting and selection
• scientific article; zbMATH DE number 3980480

Cites work

• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• On the time-space tradeoff for sorting with linear queries

Cited in

(6)

• Upper bounds for time-space trade-offs in sorting and selection
• Quantum time-space tradeoffs for sorting
• scientific article; zbMATH DE number 2119639 (Why is no real title available?)
• scientific article; zbMATH DE number 5182609 (Why is no real title available?)
• Linear-time in-place selection in less than 3n comparisons
• On the time-space tradeoff for sorting with linear queries

This page was built for publication: A simple proof of a time-space trade-off for sorting with linear comparisons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079376)