Exponential bounds for the running time of a selection algorithm

DOI10.1016/0022-0000(84)90009-6MaRDI QIDQ760796zbMATH OpenOpenAlexFDO

Authors Luc 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)

Recommendations

• Hoare's Selection Algorithm: A Markov Chain Approach
• A probabilistic analysis of the Floyd–Rivest expected time selection algorithm
• Finding the n-th largest element
• On the probabilistic worst-case time of ``find
• On the median-of-k version of Hoare's selection algorithm

Cites work

• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3620754 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Expected time bounds for selection
• Finding the median
• Probability Inequalities for Sums of Bounded Random Variables
• Time bounds for selection

Cited in

(8)

• Distributional convergence for the number of symbol comparisons used by QuickSelect
• A fixed point theorem for distributions
• The worst-case running time of the random simplex algorithm is exponential in the height
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
• Linear sorting with O(log n) processors
• Analysis of quickselect : an algorithm for order statistics
• On the median-of-k version of Hoare's selection algorithm
• A limit theorem for “quicksort”

Describes a project that uses

Uses Software

• Find
• Algorithm 489

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760796)