2019/03/19 by Fill, James Allen, Hung, Wei-Chun
#60C05 (Secondary) #68P10 (Primary) 60E05 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1903.07775
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 (log x)2; the corresponding order for the Janson (2015) bound is the lead order, x log x. 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).