Exponential bounds for the running time of a selection algorithm

DOI10.1016/0022-0000(84)90009-6zbMATH Open0555.68018OpenAlexW2048997247MaRDI QIDQ760796FDOQ760796

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

Recommendations

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

zbMATH Keywords

Hoare's selection algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Title not available (Why is that?)
• Time bounds for selection
• Title not available (Why is that?)
• Expected time bounds for selection
• Finding the median

Cited In (8)

• On the median-of-k version of Hoare's selection algorithm
• 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
• QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find
• The worst-case running time of the random simplex algorithm is exponential in the height
• Analysis of quickselect : an algorithm for order statistics

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)