Density functions for QuickQuant and QuickVal

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$andthedensityfunction$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.