Rates of convergence for Quicksort

DOI10.1016/S0196-6774(02)00206-7MaRDI QIDQ4799522zbMATH OpenOpenAlexFDO

Authors Ralph Neininger, Ludger Rüschendorf

Publication date 23 March 2003

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0196-6774(02)00206-7

zbMATH Keywords

analysis of algorithmscontraction methodlocal approximationquicksortrate of convergenceZolotarev metric

Mathematics Subject Classification ID

Searching and sorting (68P10) General topics in the theory of algorithms (68W01)

Recommendations

• Quicksort asymptotics
• A note on the Quicksort asymptotics
• Approximating the limiting quicksort distribution
• A limit theorem for “quicksort”
• Refined quicksort asymptotics

Cited in

(13)

• A general limit theorem for recursive algorithms and combinatorial structures
• Distribution of distances in random binary search trees.
• On the contraction method with degenerate limit equation.
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Almost sure convergence to the quicksort process
• Random binary trees: from the average case analysis to the asymptotics of distributions
• Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract).
• Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)
• Quicksort asymptotics
• Refined quicksort asymptotics
• A note on the Quicksort asymptotics
• On martingale tail sums for the path length in random trees
• Central limit theorem in uniform metrics for generalized Kac equations

This page was built for publication: Rates of convergence for Quicksort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4799522)