Convergence Rates in the Probabilistic Analysis of Algorithms
Ralph Neininger, Jasmin Straub · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2020
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.