Convergence Rates in the Probabilistic Analysis of Algorithms
weak convergence
probabilistic analysis of algorithms
random trees
probability metrics
- Theory of computation → Sorting and searching
- Theory of computation → Divide and conquer
Abstract. In this extended abstract a general framework is developed to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. Concrete examples from the analysis of algorithms and data structures are discussed as well as a few examples from other areas. They lead to convergence rates of polynomial and logarithmic order. Our results show how to obtain a significantly better bound for the rate of convergence when the limiting distribution is Gaussian.