Average case selection

DOI10.1145/62044.62047zbMath0674.68030OpenAlexW2016284597MaRDI QIDQ3829069

J. Ian Munro, Walter Cunto

Publication date: 1989

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

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

zbMATH Keywords

selectionprobabilistic algorithmsmedianlower boundsaverage case

Mathematics Subject Classification ID

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

Related Items (14)

Select with Groups of 3 or 4 ⋮ Determining the majority: The biased case ⋮ Finding the \(\alpha n\)-th largest element ⋮ Further analysis of the remedian algorithm ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ Unnamed Item ⋮ A stochastically quasi-optimal search algorithm for the maximum of the simple random walk ⋮ On partial sorting in restricted rounds ⋮ Finding a mediocre player ⋮ A selectable sloppy heap ⋮ Selection Algorithms with Small Groups ⋮ Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50 ⋮ On Floyd and Rivest's SELECT algorithm ⋮ On constant factors in comparison-based geometric algorithms and data structures

This page was built for publication: Average case selection