Comparison-based time-space lower bounds for selection

DOI10.1145/1721837.1721842zbMath1300.68032OpenAlexW1980190601MaRDI QIDQ2930302

Timothy M. Chan

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsrandomized algorithmstime-space trade-offsstreaming algorithmsRAMadversary argumentsmedian finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Randomized algorithms (68W20)

Related Items

Strictly in-place algorithms for permuting and inverting permutations, Finding the Median (Obliviously) with Bounded Space, Memory-constrained algorithms for simple polygons, Reprint of: Memory-constrained algorithms for simple polygons, Computing a visibility polygon using few variables, Constant work-space algorithms for facility location problems, Sorting and ranking of self-delimiting numbers with applications to tree isomorphism, Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\), Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon, Space-time trade-offs for stack-based algorithms, Finding the minimum number of elements with sum above a threshold, Priority Queues and Sorting for Read-Only Data, A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon, Selection from read-only memory with limited workspace, Unnamed Item, Computing (and Life) Is All about Tradeoffs, Finding median in read-only memory on integer input, Computing the Burrows-Wheeler transform in place and in small space