Distributional analysis of recursive algorithms by the contraction method

By means of the contraction method several interesting classes of recursions arising in the analysis of algorithms have been analyzed recently. This technique is based on the establishment of contraction properties of corresponding operators with respect to suitable probability metrics. Applications of the contraction method to the analysis of the cost of partial match queries in comparison based structures ($k$-d trees, quadtrees), the internal path lengths of random split trees (quadtrees, $m$-ary search trees), and the running time of the Find-algorithm are discussed.