Probabilistic Analysis of Recursive Algorithms and Data Structures

Abstract

A basic approach to analyze the performance of algorithms and data structures consists in exposing them to random input data and to identify asymptotically the stochastic behavior of characteristic quantities such as the running time or the space requirements needed by the algorithm or date structure. While the tools in this area are dominated by analytic techniques, recently, in particular for recursive algorithms and random trees, a more probabilistic method, so called contraction method, has been developed. In this talk I try to give an account of the present state of this method with particular emphasis on the derivation of limit laws for random recursive sequences motivated by applications from computer science.