Asymptotic analysis of a class of functional equations and applications
Journal de théorie des nombres de Bordeaux, Tome 5 (1993) no. 2, pp. 365-381.

Flajolet and Richmond have invented a method to solve a large class of divide-and-conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for z→∞ by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of N people is computed, where each person advances one step or dies with equal probabilities, and an additional “killer” can kill at any level up to d survivors, according to his probability distribution.

@article{JTNB_1993__5_2_365_0,
     author = {Grabner, P. J. and Prodinger, H. and Tichy, R. F.},
     title = {Asymptotic analysis of a class of functional equations and applications},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {365--381},
     publisher = {Universit\'e Bordeaux I},
     volume = {5},
     number = {2},
     year = {1993},
     mrnumber = {1265911},
     zbl = {0797.39008},
     language = {en},
     url = {https://www.numdam.org/item/JTNB_1993__5_2_365_0/}
}
TY  - JOUR
AU  - Grabner, P. J.
AU  - Prodinger, H.
AU  - Tichy, R. F.
TI  - Asymptotic analysis of a class of functional equations and applications
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1993
SP  - 365
EP  - 381
VL  - 5
IS  - 2
PB  - Université Bordeaux I
UR  - https://www.numdam.org/item/JTNB_1993__5_2_365_0/
LA  - en
ID  - JTNB_1993__5_2_365_0
ER  - 
%0 Journal Article
%A Grabner, P. J.
%A Prodinger, H.
%A Tichy, R. F.
%T Asymptotic analysis of a class of functional equations and applications
%J Journal de théorie des nombres de Bordeaux
%D 1993
%P 365-381
%V 5
%N 2
%I Université Bordeaux I
%U https://www.numdam.org/item/JTNB_1993__5_2_365_0/
%G en
%F JTNB_1993__5_2_365_0
Grabner, P. J.; Prodinger, H.; Tichy, R. F. Asymptotic analysis of a class of functional equations and applications. Journal de théorie des nombres de Bordeaux, Tome 5 (1993) no. 2, pp. 365-381. https://www.numdam.org/item/JTNB_1993__5_2_365_0/

[1] T.M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1984. | MR | Zbl

[2] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger and R.F. Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theoret. Comput. Sci. (to appear). | MR | Zbl

[3] P. Flajolet and L.B. Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305-320. | MR | Zbl

[4] P. Flajolet, M. Régnier and R. Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer, New York, 1985. | MR | Zbl

[5] P. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216-240. | MR | Zbl

[6] P. Flajolet and J. Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A "Algorithms and Complexity" North-Holland, 1990, 431-524. | MR | Zbl

[7] D.E. Knuth, The Art of Computer Science Vol. 3, Addison Wesley, Reading, MA, 1973.

[8] H.M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992. | MR | Zbl

[9] J.-L. Mauclaire and L. Murata, On q-Additive Functions, II, Proc. Japan Acad. 59 (1983), 441-444. | MR | Zbl

[10] H. Prodinger, How to, Advance on a Staircase by Coin Flippings,, Proceedings "Fibonacci Numbers and Applications 5" (1992) (to appear). | Zbl

[11] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927. | JFM