Ralph Neininger: Rates of Convergence for Some Recurrences

This is a joint work with Ludger Rüschendorf (Quicksort) and Hosam M. Mahmoud (distances in BST).

The normalized number of key comparisons needed to sort a list of randomly permuted items by the Quicksort algorithm is known to converge in distribution. We identify the rate of convergence to be of the order $\Theta(\ln(n)/n)$ in the Zolotarev metric. This implies several $\ln(n)/n$ estimates for other distances and local approximation results as for characteristic functions, for density approximation and for the integrated distance of the distribution functions.

With similar techniques we identify the rates of convergence for the depth of a random node and the distance of two randomly selected nodes in a random binary search tree (after normalization) to be both of the order $\Theta(1/\sqrt{\ln(n)})$ in the Zolotarev metric.

Back to the Index