Exponential bounds for the running time of a selection algorithm

DOI10.1016/0022-0000(84)90009-6zbMath0555.68018OpenAlexW2048997247MaRDI QIDQ760796

Luc P. Devroye

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90009-6

zbMATH Keywords

Hoare's selection algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

On the median-of-k version of Hoare's selection algorithm ⋮ QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find ⋮ Analysis of quickselect : an algorithm for order statistics ⋮ A fixed point theorem for distributions ⋮ A limit theorem for “quicksort” ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Linear sorting with O(log n) processors

Uses Software

• Find
• Algorithm 489

Cites Work

• Finding the median
• Time bounds for selection
• Expected time bounds for selection
• Probability Inequalities for Sums of Bounded Random Variables
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exponential bounds for the running time of a selection algorithm