QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations

DOI10.1214/19-EJP331MaRDI QIDQ2316591zbMATH OpenFDO

Authors James Allen Fill, Wei-Chun Hung

Publication date 6 August 2019

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

Full work available at URL https://arxiv.org/abs/1903.07775, https://projecteuclid.org/euclid.ejp/1561687600

zbMATH Keywords

asymptotic boundsChernoff boundslarge deviationsmoment generating functionsQuickSorttails of distributions

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probability distributions: general theory (60E05) Searching and sorting (68P10)

Abstract: We substantially refine asymptotic logarithmic upper bounds produced by Svante Janson (2015) on the right tail of the limiting QuickSort distribution function $F$ and by Fill and Hung (2018) on the right tails of the corresponding density $f$ and of the absolute derivatives of $f$ of each order. For example, we establish an upper bound on $log[1-F(x)]$ that matches conjectured asymptotics of Knessl and Szpankowski (1999) through terms of order $(logx{)}^2$; the corresponding order for the Janson (2015) bound is the lead order, $xlogx$. Using the refined asymptotic bounds on $F$, we derive right-tail large deviation (LD) results for the distribution of the number of comparisons required by QuickSort that substantially sharpen the two-sided LD results of McDiarmid and Hayward (1996).

Recommendations

• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)
• On the tails of the limiting QuickSort density
• On the tails of the limiting QuickSort density
• On the tails of the limiting Quicksort distribution
• scientific article; zbMATH DE number 1375579

Cites work

• A characterization of the set of fixed points of the quicksort transformation
• A limit theorem for “quicksort”
• A limiting distribution for quicksort
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1375579 (Why is no real title available?)
• scientific article; zbMATH DE number 1552325 (Why is no real title available?)
• Large Deviations for Quicksort
• Multiway trees of maximum and minimum probability under the random permutation model
• On the tails of the limiting QuickSort density
• On the tails of the limiting Quicksort distribution
• Quicksort asymptotics
• QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations

Cited in

(12)

• On the tails of the limiting QuickSort density
• QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations
• Asymptotic distributions for random median quicksort
• Density functions for \texttt{QuickQuant} and \texttt{QuickVal}
• scientific article; zbMATH DE number 1375579 (Why is no real title available?)
• Large Deviations for Quicksort
• A note concerning the limit distribution of the quicksort algorithm
• Refined quicksort asymptotics
• On the tails of the limiting QuickSort density
• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)
• A note on the Quicksort asymptotics
• On the tails of the limiting Quicksort distribution

This page was built for publication: QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations

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