×

zbMATH — the first resource for mathematics

Mellin transforms and asymptotics: Harmonic sums. (English) Zbl 0869.68057
Summary: This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models, and the average-case analysis of algorithms. It relies on the Mellin transform, a close relative of the integral transforms of Laplace and Fourier. The method applies to harmonic sums that are superpositions of rather arbitrary “harmonics” of a common base function. Its principle is a precise correspondence between individual terms in the asymptotic expansion of an original function and singularities of the transformed function. The main applications are in the area of digital data structures, probabilistic algorithms, and communication theory.

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] a reprint of the 10th National Bureau of Standards edition, 1964.
[2] Allouche, J.-P.; Cohen, H., Dirichlet series and curious infinite products, Bull. London math. soc., 17, 531-538, (1985) · Zbl 0577.10036
[3] Andrews, G.E., Encyclopedia of mathematics and its application, () · Zbl 0152.05202
[4] Apostol, T.M., Introduction to analytic number theory, (1976), Springer Berlin · Zbl 0335.10001
[5] Apostol, T.M.; Vu, T.H., Dirichlet series related to the Riemann zeta function, J. number theory, 19, 85-102, (1984) · Zbl 0539.10032
[6] Barnes, E.W., The Maclaurin sum formula, (), 253-272 · JFM 36.0328.03
[7] Bellman, R., Analytic number theory, an introduction, (1980), Benjamin-Cummings Reading · Zbl 0448.10001
[8] Berndt, B.C., (), Part II · Zbl 0716.11001
[9] Berndt, B.C.; Evans, R.J., Extensions of asymptotic expansions from chapter 15 of Ramanujan’s second notebook, J. reine angew. math., 361, 118-134, (1985) · Zbl 0571.41027
[10] Borwein, J.M.; Borwein, P.B.; Shail, R., Analysis of certain lattice sums, J. math. anal. appl., 143, 126-137, (1989) · Zbl 0682.10028
[11] Comtet, L., Advanced combinatorics, (1974), Reidel Dordrecht
[12] Davenport, H., Multiplicative number theory, (1980), Springer New York, revised by H.L. Montgomery
[13] Davies, B., Integral transforms and their applications, (1978), Springer Berlin · Zbl 0381.44001
[14] reprinted from Koninkl. Nederl. Akademie Wetenschappen, Ser. A. · Zbl 0030.34502
[15] a reprint of the third North-Holland edition, 1970 (first edition, 1958). · Zbl 0556.41021
[16] De Bruijn, N.G.; Knuth, D.E.; Rice, S.O., The average height of planted plane trees, (), 15-22 · Zbl 0247.05106
[17] Dingle, R.B., Asymptotic expansions: their derivation and interpretation, (1973), Academic Press London · Zbl 0279.41030
[18] Doetsch, G., ()
[19] Erdélyi, A.; Magnus, W.; Oberhettinger, F.; Tricomi, F.G., Tables of integral transforms, (1954), McGraw-Hill New York · Zbl 0055.36401
[20] Fayolle, G.; Flajolet, P.; Hofri, M., On a functional equation arising in the analysis of a protocol for multiaccess broadcast channel, Adv. appl. probab., 18, 441-472, (1986) · Zbl 0625.94001
[21] Feller, W., ()
[22] Flajolet, P., Approximate counting: a detailed analysis, Bit, 25, 113-134, (1985) · Zbl 0562.68027
[23] Flajolet, P., On adaptive sampling, Computing, 34, 391-400, (1990) · Zbl 0689.68014
[24] Flajolet, P.; Golin, M.; Flajolet, P.; Golin, M., Exact asymptotics of divide-and-conquer recurrences, (), 137-149 · Zbl 1418.68252
[25] Flajolet, P.; Golin, M., Mellin transforms and asymptotics: the mergesort recurrence, Acta inform., 31, 673-696, (1994) · Zbl 0818.68064
[26] Flajolet, P.; Grabner, P.; Kirschenhofer, P.; Prodinger, H.; Tichy, R., Mellin transforms and asymptotics: digital sums, Theoret. comput. sci., 123, 291-344, (1994) · Zbl 0788.44004
[27] Flajolet, P.; Martin, G.N., Probabilistic counting algorithms for data base applications, J. comput. system sci., 31, 182-209, (1985) · Zbl 0583.68059
[28] Flajolet, P.; Prodinger, H., Register allocation for unary-binary trees, SIAM J. comput., 15, 629-640, (1986) · Zbl 0612.68065
[29] Flajolet, P.; Puech, C., Partial match retrieval of multidimensional data, J. ACM, 33, 371-407, (1986)
[30] Flajolet, P.; Raoult, J.-C.; Vuillemin, J., The number of registers required to evaluate arithmetic expressions, Theoret. comput. sci., 9, 99-125, (1979) · Zbl 0407.68057
[31] Flajolet, P.; Régnier, M.; Sedgewick, R., Some uses of the Mellin integral transform in the analysis of algorithms, (), 241-254, (Invited Lecture)
[32] Flajolet, P.; Richmond, B., Generalized digital trees and their difference-differential equations, Random struct. algorithms, 3, 305-320, (1992) · Zbl 0758.60015
[33] Flajolet, P.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, Theoret. comput. sci., 79, 37-109, (1991) · Zbl 0768.68041
[34] Flajolet, P.; Sedgewick, R., Mellin transforms and asymptotics: finite differences and Rice’s integrals, Theoret. comput. sci., 144, 101-124, (1995), this volume · Zbl 0869.68056
[35] Fredman, M.L.; Knuth, D.E., Recurrence relations based on minimization, J. math. anal. appl., 48, 534-559, (1974) · Zbl 0312.65091
[36] Gonnet, G.H., Notes on the derivation of asymptotic expressions from summations, Inform. process. lett., 7, 4, 165-169, (1978) · Zbl 0386.65001
[37] Gonnet, G.H.; Baeza-Yates, R., ()
[38] Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley New York · Zbl 0519.05001
[39] Greenberg, A.G.; Flajolet, P.; Ladner, R.E., Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, J. ACM, 34, 289-325, (1987) · Zbl 0634.94002
[40] reprinted and corrected from the first edition, Cambridge, 1940.
[41] Hardy, G.H.; Riesz, M., The general theory of Dirichlet’s series, () · JFM 45.0387.03
[42] Hecke, E., Lectures on Dirichlet series, modular functions and quadratic forms, () · Zbl 0507.10015
[43] Henrici, P., Applied and computational complex analysis, (1977), Wiley New York · Zbl 0377.30002
[44] Hofri, M., Probabilistic analysis of algorithms, (1987), Springer Berlin
[45] Jacquet, P.; Régnier, M.; Jacquet, P.; Régnier, M., Trie partitioning process: limiting distributions, (), 196-210 · Zbl 0605.68057
[46] Jacquet, P.; Szpankowski, W., Ultimate characterizations of the burst response of an interval searching algorithm: a study of a functional equation, SIAM J. comput., 18, 777-791, (1989) · Zbl 0679.68052
[47] Jacquet, P.; Szpankowski, W., Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, (1991), preprint
[48] Jacquet, P.; Szpankowski, W., Autocorrelation on words and its applications: analysis of suffix trees by string-ruler approach, J. combin. theory ser. A, 66, 237-269, (1994) · Zbl 0802.68097
[49] Jorgenson, J.A.; Lang, S., Basic analysis of regularized series and products, () · Zbl 0788.30003
[50] Kemp, R., The average number of registers needed to evaluate a binary tree optimally, Acta inform., 11, 363-372, (1979) · Zbl 0395.68059
[51] Kemp, R., Fundamentals of the average case analysis of particular algorithms, (1984), Wiley-Teubner Stuttgart · Zbl 0638.68026
[52] Kirschenhofer, P.; Martinez, C.; Prodinger, H., Analysis of an optimized search algorithm for skip lists, (), 21
[53] Kirschenhofer, P.; Prodinger, H., On some applications of formulae of Ramanujan in the analysis of algorithms, Mathematika, 38, 14-33, (1991) · Zbl 0765.68051
[54] 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
[55] Klusch, D., The sampling theorem, Dirichlet series and Hankel transforms, J. comput. appl. math., 44, 261-273, (1992) · Zbl 0768.94004
[56] Knuth, D.E., The art of computer programming, () · Zbl 0191.17903
[57] Knuth, D.E., The average time for carry propagation, Indagationes math., 40, 238-242, (1978) · Zbl 0382.10035
[58] ()
[59] Lindelöf, E., Robert hjalmar Mellin, Advances in mathematics, Vol. 61, i-vi, (1993), (H. Mellin’s notice and bibliography) · JFM 59.0034.02
[60] ()
[61] Macfarlane, G.G., The application of Mellin transforms to the summation of slowly converging series, Philos. mag., 40, 188-197, (1949) · Zbl 0032.07601
[62] Mahmoud, H., Evolution of random search trees, (1992), Wiley New York · Zbl 0762.68033
[63] Mathys, P.; Flajolet, P., Q-ary collision resolution algorithms in random access systems with free or blocked channel access, IEEE trans. inform. theory, IT-31, 217-243, (1985) · Zbl 0566.94001
[64] Mellin, H., Die Dirichlet’schen reihen, die zahlentheoretischen funktionen und die endlichen produkte von endlichem geshlecht, Acta math., 28, 37-64, (1904) · JFM 35.0218.02
[65] Mellin, H., Abriβ einer einheitlichen theorie der gamma- und der hypergeometrischen funktionen, Math. ann., 68, 305-337, (1910) · JFM 41.0500.04
[66] Oberhettinger, F., Tables of Mellin transforms, (), 275
[67] Oberhettinger, F., Tables of Fourier transforms and Fourier transforms of distributions, (1990), Springer Berlin · Zbl 0694.42017
[68] Odlyzko, A.M., Enumeration of string, (), 205-228 · Zbl 0484.30002
[69] Pippenger, N., An elementary approach to some analytic asymptotics, SIAM J. math. anal., 24, 1361-1377, (1993) · Zbl 0828.26003
[70] Prodinger, H., How to select a loser, Discrete math., 120, 149-159, (1993) · Zbl 0795.90103
[71] Prodinger, H., Hypothetical analyses: approximate counting in the style of Knuth, path length in the style of flajolet, Theoret. comput. sci., 100, 243-251, (1993) · Zbl 0747.68032
[72] Régnier, M., Evaluation des performances du hachage dynamique, ()
[73] Régnier, M., Analysis of grid file algorithms, Bit, 25, 335-357, (1985) · Zbl 0568.68076
[74] Reingold, E.M.; Supowit, K.J., Probabilistic analysis of divide-and-conquer heuristics for minimum weighted Euclidean matching, Networks, 13, 49-66, (1983) · Zbl 0503.68051
[75] Sedgewick, R., Data movement in odd-even merging, SIAM J. comput., 7, 239-272, (1978) · Zbl 0379.68024
[76] Sedgewick, R., Algorithms, (1988), Addison-Wesley Reading, MA
[77] Sneddon, I.N., The use of integral transforms, (1972), McGraw-Hill New York · Zbl 0265.73085
[78] Stanley, R.P., ()
[79] Szpankowski, W., Some results on V-ary asymmetric tries, J. algorithms, 9, 224-244, (1988) · Zbl 0637.68072
[80] Szpankowski, W., Patricia tries again revisited, J. ACM, 37, 691-711, (1990) · Zbl 0711.68065
[81] Titchmarsh, E.C., The theory of functions, (1939), Oxford Univ. Press Oxford · Zbl 0022.14602
[82] reprinted from the second edition, Oxford, 1948. · Zbl 0601.10026
[83] Titchmarsh, E.C.; Heath-Brown, D.R., The theory of the Riemann zeta-function, (1986), Oxford Science Publications
[84] Vitter, J.S.; Flajolet, P., Analysis of algorithms and data structures, (), 431-524, ch. 9 · Zbl 0900.68251
[85] Whittaker, E.T.; Watson, G.N., A course of modern analysis, (1927), Cambridge Univ. Press Cambridge, reprinted 1973 · Zbl 0108.26903
[86] Widder, D.V., The Laplace transform, (1941), Princeton Univ. Press Princeton, NJ · Zbl 0060.24801
[87] Wilf, H.S., Generatingfunctionology, (1990), Academic Press New York · Zbl 0689.05001
[88] Wong, R., Asymptotic approximations of integrals, (1989), Academic Press New York · Zbl 0679.41001
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.