QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find
From MaRDI portal
Publication:3191202
DOI10.1017/S0963548314000121zbMath1329.60082MaRDI QIDQ3191202
James Allen Fill, Jason Matterer
Publication date: 24 September 2014
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Related Items (3)
Towards a realistic analysis of the QuickSelect algorithm ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Process convergence for the complexity of radix selection on Markov sources
Cites Work
- Multiple Quickselect -- Hoare's Find algorithm for several elements
- Exponential bounds for the running time of a selection algorithm
- Simulating the Dickman distribution
- Perfect simulation of Vervaat perpetuities
- Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009. Proceedings, Part I
- Probabilistic analysis of multiple quick select
- Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
- Distributional convergence for the number of symbol comparisons used by QuickSort
- Analysis of the expected number of bit comparisons required by quickselect
- On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
- Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
- Probability with Martingales
- Hoare's Selection Algorithm: A Markov Chain Approach
- Asymptotic distribution theory for Hoare's selection algorithm
- Probability and Computing
- On the probabilistic worst-case time of ``find
This page was built for publication: QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find
