Divide-and-conquer recurrences - Classification of asymptotics

被引：0

作者：

Derfel G. ^{[1
]}

Vogl F. ^{[2
]}

机构：

[1] Dept. of Mathematics and Computer Science, Ben Gurion University, Beer Sheva 84105

[2] Abt. F. Techn. Mathematik, TU Wien, A-1040 Wien

来源：

aequationes mathematicae | 2000年 / 60卷 / 3期

关键词：

Generate Function; Computer Science; Functional Equation; Recurrence Equation; Exponential Generate;

D O I：

10.1007/PL00000132

中图分类号：

学科分类号：

摘要：

We deal with a class of recurrence equations arising in the theory of algorithms, stochastic pocesses, computer science, etc. and give a classification theorem for asymptotics of their solutions. The method of the proof is based upon consideration of the exponential generating function, which is a solution of a linear nonhomogeneous functional equation with rescaling. © Birkhäuser Verlag, Basel, 2000.

引用

页码：243 / 257

页数：14

共 16 条

[1]

Adams C.R., On the linear ordinary q-difference equation, Ann. of Math., 30, 2, pp. 195-205, (1929)

[2]

Derfel G., Thuswaldner J., Tichy R., Vogl F., Asymptotic analysis of a class of functional equations, Aequations Math., 55, pp. 91-105, (1998)

[3]

Drmota M., Tichy R., Sequences, Discrepancies and Applications, Lecture Notes in Math., 1651, (1997)

[4]

Flajolet P., Singularity analysis and asymptotics of Bernoulli sums, Theoretical Computer Science, 215, pp. 371-381, (1999)

[5]

Flajolet P., Odlyzko A., Singularity analysis of generating functions, SIAM J. Discrete Mathematics, 3, 2, pp. 216-240, (1990)

[6]

Flajolet P., Richmond B., Generalized digital trees and their difference-differential equations, Random Structures and Algorithms, 3, 3, pp. 305-320, (1992)

[7]

Flajolet P., Sedgewick R., Digital search trees revisited, SIAM J. Comput., 15, pp. 748-767, (1986)

[8]

Hosking J.R.M., Moments of order statistics of Cantor distribution, Statist. Probab. Lett., 19, pp. 161-165, (1994)

[9]

Jacquet P., Szpankowski W., Analytical depoissonisation and its application, Theoretical Computer Science (Fundamental Studies Section), 201, 1-2, pp. 1-62, (1998)

[10]

Knuth D.E., The Art of Computer Programming, 3, (1973)

← 1 2 →