On the time-space tradeoff for sorting with linear queries

DOI10.1016/0304-3975(82)90060-3zbMath0547.68062OpenAlexW2027988279MaRDI QIDQ799115

Andrew Chi-Chih Yao

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90060-3

zbMATH Keywords

sortingtime-space tradeoffbranching programslinear queries

Mathematics Subject Classification ID

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

Related Items (4)

A simple proof of a time-space trade-off for sorting with linear comparisons ⋮ Two time-space tradeoffs for element distinctness ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Time-space tradeoffs for set operations

Cites Work

• Unnamed Item
• Some Monotonicity Properties of Partial Orders
• A Counting Approach to Lower Bounds for Selection Problems

This page was built for publication: On the time-space tradeoff for sorting with linear queries