On the tails of the limiting QuickSort density

DOI10.1214/19-ECP213MaRDI QIDQ1725502zbMATH OpenOpenAlexFDO

Authors James Allen Fill, Wei-Chun Hung

Publication date 14 February 2019

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

Full work available at URL https://arxiv.org/abs/1808.00643, https://projecteuclid.org/euclid.ecp/1550113298

zbMATH Keywords

Landau-Kolmogorov inequalityasymptotic boundsQuickSortdensity tails

Mathematics Subject Classification ID

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

Abstract: We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar bounds on absolute values of derivatives of f of each order.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3114499 (Why is no real title available?)
• scientific article; zbMATH DE number 1375579 (Why is no real title available?)
• scientific article; zbMATH DE number 50600 (Why is no real title available?)
• scientific article; zbMATH DE number 1552325 (Why is no real title available?)
• A characterization of the set of fixed points of the quicksort transformation
• A limit theorem for “quicksort”
• A limiting distribution for quicksort
• Inequalities between the upper bounds of the derivatives of an arbitrary function on the half-line
• On the tails of the limiting Quicksort distribution

Cited in

(8)

• A limit theorem for “quicksort”
• Logarithmic integrals, zeta values, and tiered binomial coefficients
• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)
• On the tails of the limiting Quicksort distribution
• Upper tail analysis of bucket sort and random tries
• On the tails of the limiting QuickSort density
• QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations
• scientific article; zbMATH DE number 1552325 (Why is no real title available?)

This page was built for publication: On the tails of the limiting QuickSort density

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