On the probabilistic worst-case time of ``find

DOI10.1007/s00453-001-0046-2zbMath1021.68030OpenAlexW2030156152MaRDI QIDQ5953102

Luc P. Devroye

Publication date: 14 January 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0046-2

zbMATH Keywords

Hoare's selection algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find ⋮ Stochastic recursions on directed random graphs ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ The analysis of range quickselect and related problems ⋮ The functional equation of the smoothing transform ⋮ A survey of max-type recursive distributional equations ⋮ On stochastic recursive equations of sum and max type ⋮ Convergence of the population dynamics algorithm in the Wasserstein metric ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect