Optimal Time Minimal Space Selection Algorithms

DOI10.1145/322261.322264zbMath0461.68061OpenAlexW1969562600MaRDI QIDQ3911405

David P. Dobkin, J. Ian Munro

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322261.322264

zbMATH Keywords

sortingmedianlower boundlinear-time algorithm

Mathematics Subject Classification ID

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

Related Items (4)

Near-optimal online multiselection in internal and external memory ⋮ Learning nested concept classes with limited storage ⋮ Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50 ⋮ Computing the Burrows-Wheeler transform in place and in small space

This page was built for publication: Optimal Time Minimal Space Selection Algorithms