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 in the Zolotarev metric. This implies several 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 in the Zolotarev metric.
Back to the Index