Quicksort asymptotics
From MaRDI portal
Publication:4799520
DOI10.1016/S0196-6774(02)00216-XzbMath1011.68028arXivmath/0105248MaRDI QIDQ4799520
James Allen Fill, Svante Janson
Publication date: 23 March 2003
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0105248
rate of convergence; asymptotics; density; moment generating function; coupling; limit distribution; numerical analysis; Quicksort; sorting algorithm; Kolmogorov-Smirnov distance; \(d_2\)-metric
Related Items
Refined quicksort asymptotics, A note on the quicksort asymptotics, On martingale tail sums for the path length in random trees, Upper tail analysis of bucket sort and random tries, Upper tail analysis of bucket sort and random tries, Approximating perpetuities, The total path length of split trees, Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates, An efficient algorithm for overcomplete sparsifying transform learning with signal denoising, Distributional convergence for the number of symbol comparisons used by QuickSort, 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, QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations, Density functions for \texttt{QuickQuant} and \texttt{QuickVal}, A weakly 1-stable distribution for the number of random records and cuttings in split trees, Random Records and Cuttings in Binary Search Trees, Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
