• Theory of computation → Sorting and searching
  • Theory of computation → Divide and conquer
Ralph Neininger
Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany
Jasmin Straub
Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany

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.