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

DOI10.1016/0304-3975(86)90185-4zbMath0597.68052OpenAlexW2063879799MaRDI QIDQ1079376

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

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

Cites Work

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

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