Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm

DOI10.1214/18-EJP227zbMath1403.60026arXiv1703.00505MaRDI QIDQ1994506

Larry Goldstein

Publication date: 1 November 2018

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.00505

zbMATH Keywords

complexitysortingdistributional approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Central limit and other weak theorems (60F05) Searching and sorting (68P10)

Related Items (5)

Relaxation of monotone coupling conditions: Poisson approximation and beyond ⋮ Zero bias enhanced Stein couplings ⋮ Convergence to scale-invariant Poisson processes and applications in Dickman approximation ⋮ Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm ⋮ Dickman approximation in simulation, summations and perpetuities

Uses Software

• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation by the Dickman distribution and quasi-log arithmic combinatorial structures
• Simulating the Dickman distribution
• Logarithmic combinatorial structures: A probabilistic approach
• On the strange domain of attraction to generalized Dickman distributions for sums of independent random variables
• Analysis of the expected number of bit comparisons required by quickselect
• Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm
• Quickselect and the Dickman Function
• Random minimal directed spanning trees and Dickman-type distributions
• Quicksort asymptotics
• A statistical view on exchanges in Quickselect

This page was built for publication: Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm