Thomas Preu

Rice's integrals -- a method for solving generalized differences

Abstract

Often in the analysis of algorithm and data structures we have the need to estimate the asymptotic growth of differences and sequences defined by recurrence equations. But often we don't know the explicit representation of the solutions. Therefor we need methods, which we can establish asymptotics without knowing the exact representation. Rice's integral is such a method. In this paper we will introduce basics in complex analysis and develope the mathematic foundations needed in theoretical computer science. The paper is based on the lecture "Analysis 4" held by Prof. W. Heise in 2003 at the TU München and an article by Flajolet et al..