On the time-space tradeoff for sorting with linear queries

DOI10.1016/0304-3975(82)90060-3zbMATH Open0547.68062OpenAlexW2027988279MaRDI QIDQ799115FDOQ799115

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

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

zbMATH Keywords

sortingbranching programstime-space tradeofflinear queries

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Some Monotonicity Properties of Partial Orders
• A Counting Approach to Lower Bounds for Selection Problems

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)