Density functions for QuickQuant and QuickVal

2021/09/29 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.2109.14749

Abstract

We prove that, for every 0 ≤ t ≤ 1, the limiting distribution of the scale-normalized number of key comparisons used by the celebrated algorithm QuickQuant to find the tth quantile in a randomly ordered list has a Lipschitz continuous density function f_t that is bounded above by 10. Furthermore, this density f_t(x) is positive for every x > min\t, 1 - t\ and, uniformly in t, enjoys superexponential decay in the right tail. We also prove that the survival function 1 - F_t(x) = ∫_x^∞ f_t(y) dy and the density function f_t(x) both have the right tail asymptotics exp [-x ln x - x ln ln x + O(x)]. We use the right-tail asymptotics to bound large deviations for the scale-normalized number of key comparisons used by QuickQuant.

Related

• Smoothness and decay properties of the limiting Quicksort density function
• On the tails of the limiting QuickSort density
• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations
• Convergence of the QuickVal Residual
• On fine fluctuations of the complexity of the QuickSelect algorithm