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 convergenceasymptoticsdensitymoment generating functioncouplinglimit distributionnumerical analysisQuicksortsorting algorithmKolmogorov-Smirnov distance\(d_2\)-metric
Related Items (17)
Approximating perpetuities ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm ⋮ The total path length of split trees ⋮ On martingale tail sums for the path length in random trees ⋮ Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise ⋮ Random Records and Cuttings in Binary Search Trees ⋮ An efficient algorithm for overcomplete sparsifying transform learning with signal denoising ⋮ Refined quicksort asymptotics ⋮ Upper tail analysis of bucket sort and random tries ⋮ Upper tail analysis of bucket sort and random tries ⋮ QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations ⋮ A note on the quicksort asymptotics
This page was built for publication: Quicksort asymptotics