zbMATH — the first resource for mathematics

The evaluation of an alternative sum with applications to the analysis of some data structures. (English) Zbl 0657.68071
In the analysis of digital search trees and similar data structures like tries and Patricia tries there occur alternating sums the asymptotic analysis of which is nontrivial because the single terms are of almost equal size. The author shows how expressions of that type may be analyzed using Mellin transform techniques.
Reviewer: P.Kirschenhofer

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Abramowitz, M.; Stegun, L., Handbook of mathematical functions, (1964), Dover New York · Zbl 0171.38503
[2] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., Data structures and algorithms, (1983), Addison-Wesley Reading, MA · Zbl 0307.68053
[3] Flajolet, Ph., On the performance evaluation of extendible hashing and trie searching, Acta informatica, 20, 345-369, (1983) · Zbl 0515.68048
[4] Flajolet, Ph.; Sedgewick, R., The asymptotic evaluation of some alternative sums involving binomial coefficients, (March 1983), Preprint
[5] Flajolet, Ph.; Sedgewick, R., Digital search trees revisited, SIAM J. comput., 15, 748-767, (1986) · Zbl 0611.68041
[6] Henrici, P., Applied and computational complex analysis, (1977), Wiley New York · Zbl 0377.30002
[7] Hofri, M., Stack algorithms for collision-detecting channels and their analysis: A limited survey, Proc. internat. seminar on modeling and performance evaluation methodology, 53-78, (1983), Paris
[8] Kirschenhofer, P.; Prodinger, H., Some further results on digital trees, (), 177-185
[9] Knuth, D.E., The art of computer programming: sorting and searching, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[10] Mathys, P.; Flajolet, Ph., Q-ary collision resolution algorithms in random-access systems with free and blocked channel access, IEEE trans. inform. theory, IT-31, 217-243, (1985) · Zbl 0566.94001
[11] Riordan, J., Combinatorial identities, (1968), Wiley New York · Zbl 0194.00502
[12] Szpankowski, W., On a recurrence equation arising in the analysis of conflict resolution algorithms, Stochastic models, 3, 89-144, (1987) · Zbl 0624.94006
[13] Szpankowski, W., Solution of a linear recurrence equation arising in the analysis of some algorithms, SIAM J. algebraic & discrete methods, 8, 233-250, (1987) · Zbl 0648.68059
[14] Szpankowski, W., Some results on V-ary asymmetric tries, J. algorithms, 9, 224-244, (1988) · Zbl 0637.68072
[15] Szpankowski, W., Two problems on the average complexity of digital trees, Proc. internat. conf. on performance ’87, 189-208, (1987), Brussels
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.