Density functions for QuickQuant and QuickVal

Abstract

We prove that, for every $0\le t\le 1$, the limiting distribution of the scale-normalized number of key comparisons used by the celebrated algorithm QuickQuant to find the $t$th 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)={\int }_x^{\infty }{f}_t(y)\mathrm{d}y$ 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.

72 pages; submitted for publication in September, 2021