The contraction method for recursive algorithms

In this paper we give an introduction to the analysis of algorithms by the contraction method. By means of this method several interesting classes of recursions can be analyzed as particular cases of our general framework. We introduce the main steps of this technique which is based on contraction properties of the algorithm with respect to suitable probability metrics. Typically the limiting distribution is characterized as a fixed point of a limiting operator on the class of probability distributions. We explain this method in the context of several ‘divide and conquer’ algorithms. In the second part of the paper we introduce a new quite general model for branching dynamical systems and explain that the contraction method can be applied in this model. This model includes many classical examples of random trees and gives a general frame for further applications.