Two not-that-dull functional equations arising in the analysis of algorithms

We shall talk about two functional equations arising in the analysis of algorithms, namely, in the performance evaluation of the generalized digital search trees and the asymmetric leader election algorithm. These functional equations deal with Poisson transforms of the general recurrence $$ x_{n+b}=a_n+ c p^n x_n + u \sum_{k=0}^n {n \choose k} p^k (1-p)^{n-k} (x_k+x_{n-k}), $$ where $u$ and $c$ are constants, $a_n$ is a given sequence, and $b\geq 1$ is a parameter. Together with suitable initial condition, this recurrence describes both algorithms. It was extensively investigated either for $b=1$ or $c=0$. We present asymptotic expansions of $x_n$ up to $O(1)$ term. Interestingly enough, for both algorithms there appears a constant that must be evaluated numerically from the original recurrence. Analytic techniques of (precise) analysis of algorithms are used to establish these conclusions. In particular, we use analytic poissonization/depoissonization, Mellin transform and singularity analysis. The results presented in this talk were obtained jointly with S. Janson, G. Louchard and J. Tang.