On the tails of the limiting QuickSort density

Electronic Communications in Probability

James Allen Fill¹ 

关键词: QuickSort;    density tails;    asymptotic bounds;    Landau–Kolmogorov inequality;   

DOI  :  10.1214/19-ECP213

学科分类：统计和概率

来源: Institute of Mathematical Statistics

【 摘 要 】

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.

【 授权许可】

CC BY