On the time-space tradeoff for sorting with linear queries

DOI10.1016/0304-3975(82)90060-3MaRDI QIDQ799115zbMATH OpenOpenAlexFDO

Authors 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

sortingbranching programstime-space tradeofflinear queries

Mathematics Subject Classification ID

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

Recommendations

• A simple proof of a time-space trade-off for sorting with linear comparisons
• A Time-Space Tradeoff for Element Distinctness
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Quantum time-space tradeoffs for sorting
• Upper bounds for time-space trade-offs in sorting and selection

Cites work

• scientific article; zbMATH DE number 3499229 (Why is no real title available?)
• A Counting Approach to Lower Bounds for Selection Problems
• Some Monotonicity Properties of Partial Orders

Cited in

(10)

• Two time-space tradeoffs for element distinctness
• Space-time trade-offs for some ranking and searching queries
• A time-space tradeoff for sorting on non-oblivious machines
• Upper bounds for time-space trade-offs in sorting and selection
• Sorting in linear time?
• On-line sorting of twisted sequences in linear time
• Linear-time in-place selection in less than 3n comparisons
• Quantum time-space tradeoffs for sorting
• Time-space tradeoffs for set operations
• A simple proof of a time-space trade-off for sorting with linear comparisons

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

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