×

zbMATH — the first resource for mathematics

Mellin transforms and asymptotics: Finite differences and Rice’s integrals. (English) Zbl 0869.68056
Summary: High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin transform asymptotics, is put in perspective and illustrated by means of several examples related to combinatorics and the analysis of algorithms like digital tries, digital search trees, quadtrees, and distributed leader election.

MSC:
68Q25 Analysis of algorithms and problem complexity
44A15 Special integral transforms (Legendre, Hilbert, etc.)
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berndt, B.C., (), Part I
[2] Buchta, C., On the average number of maxima in a set of vectors, Inform. process. lett., 33, 63-65, (1989) · Zbl 0682.68041
[3] Comtet, L., Advanced combinatorics, (1974), Reidel Dordrecht
[4] Dingle, R.B., Asymptotic expansions: their derivation and interpretation, (1973), Academic Press London · Zbl 0279.41030
[5] Doetsch, G., ()
[6] Flajolet, P.; Gourdon, X.; Dumas, P., Mellin transforms and asymptotics: harmonic sums, Theoret. comput. sci., 144, 3-58, (1995) · Zbl 0869.68057
[7] Flajolet, P.; Grabner, P.; Kirschenhofer, P.; Prodinger, H.; Tichy, R., Mellin transforms and asymptotics: digital sums, Theoret. comput. sci., 123, 2, 291-314, (1994) · Zbl 0788.44004
[8] Flajolet, P.; Labelle, G.; Laforest, L.; Salvy, B., Hypergeometrics and the cost structure of quadtrees, (), 26 pages · Zbl 0834.68013
[9] Flajolet, P.; Odlyzko, A.M., Singularity analysis of generating functions, SIAM J. discrete math., 3, 2, 216-240, (1990) · Zbl 0712.05004
[10] Flajolet, P.; Régnier, M.; Sedgewick, R., Some uses of the Mellin integral transform in the analysis of algorithms, (), 241-254, (invited lecture)
[11] Flajolet, P.; Régnier, M.; Sotteau, D., Algebraic methods for trie statistics, (), 145-188, (invited lecture)
[12] Flajolet, P.; Richmond, B., Generalized digital trees and their difference-differential equations, Random structures and algorithms, 3, 3, 305-320, (1992) · Zbl 0758.60015
[13] Flajolet, P.; Sedgewick, R., The asymptotic evaluation of some alternating sums involving binomial coefficients, (1983), unpublished memoir
[14] Flajolet, P.; Sedgewick, R., Digital search trees revisited, SIAM J. comput., 15, 3, 748-767, (1986) · Zbl 0611.68041
[15] Hardy, G.H., Divergent series, (1947), Oxford University Press Oxford · Zbl 0897.01044
[16] Hardy, G.H., (), (Reprinted and Corrected from the 1st ed., Cambridge, 1940)
[17] Jordan, C., Calculus of finite differences, (1965), Chelsea New York, (1st ed., Budapest, 1939) · Zbl 0154.33901
[18] Kirschenhofer, P.; Prodinger, H., Multidimensional digital searching — alternative data structures, Random structures and algorithms, 5, 1, 123-134, (1994) · Zbl 0803.68024
[19] Kirschenhofer, P.; Prodinger, H.; Szpankowski, W., On the variance of the external path length in a symmetric digital trie, Discrete appl. math., 25, 129-143, (1989) · Zbl 0685.68059
[20] Kirschenhofer, P.; Prodinger, H.; Szpankowski, W., Multidimensional digital searching and some new parameters of tries, Internal. J. found. comput. sci., 4, 1, 69-84, (1993) · Zbl 0782.68061
[21] Knuth, D.E., The art of computer programming, vol. 3: sorting and searching, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[22] Mahmoud, H., Evolution of random search trees, (1992), Wiley New York · Zbl 0762.68033
[23] Milne-Thomson, L.M., The calculus of finite differences, (1981), Chelsea New York, reprinted from the original edition, London, 1933) · Zbl 0477.39001
[24] Nörlund, N.F., Vorlesungen über differenzenrechnung, (1954), Chelsea New York · JFM 50.0315.02
[25] Odlyzko, A.M., Asymptotic enumeration methods, (), preprint · Zbl 0845.05005
[26] Prodinger, H., How to select a loser, Discrete math., 120, 149-159, (1993) · Zbl 0795.90103
[27] Prodinger, H., Hypothetical analyses: approximate counting in the style of Knuth, path length in the style of flajolet, Theoret. comput. sci., 100, 1, 243-251, (1993) · Zbl 0747.68032
[28] Szpankowski, W., The evaluation of an alternative [sic!] sum with applications to the analysis of algorithms, Inform. process. lett., 28, 13-19, (1988) · Zbl 0657.68071
[29] Szpankowski, W., Some results on V-ary asymmetric tries, J. algorithms, 9, 224-244, (1988) · Zbl 0637.68072
[30] Szpankowski, W., Patricia tries again revisited, J. ACM, 37, 4, 691-711, (1990) · Zbl 0711.68065
[31] Szpankowski, W., A characterization of digital search trees from the successful search viewpoint, Theoret. comput. sci., 85, 117-134, (1991) · Zbl 0746.68027
[32] Titchmarsh, E.C.; Heath-Brown, D.R., The theory of the Riemann zeta-function, (1986), Oxford Science Publications Oxford
[33] Whittaker, E.T.; Watson, G.N., A course of modern analysis, (1927), Cambridge University Press Compridge, (reprinted 1973) · Zbl 0108.26903
[34] Wimp, J.; Zeilberger, D., Resurrecting the asymptotics of linear recurrences, J. math. anal. appl., 111, 162-176, (1985) · Zbl 0579.05007
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.