Transcription
Dr Flajolet’s elixir or Mellintransform and asymptoticsPhilippe DumasMellin transform and fundamental stripSymbolic analysisFundamental resultHarmonic sumsZigzag methodAverage-case analysis of algorithms and harmonic sumsExponentials in harmonic sumsTechnical pointOscillationsRelated topics4567789101112PRIMARY PAPERS (fix these references)[[PF058]] Partial match retrieval of multidimensional data[[PF052]] Some uses of the Mellin integral transform in the analysis of algorithms[[PF101]] Generalized digital trees and their difference-differential equations[[PF120]] Mellin transforms and asymptotics: Harmonic sums[[PF124]] Mellin transforms and asymptotics: Finite differences and Rice’s integrals[[PF125]] Asymptotique des récurrences mahlériennes : le cas cyclotomique[[PF129]] The average case analysis of algorithms: Mellin transform asymptoticsSECONDARY PAPERSFrom Analytic Combinatorics (Vol I): [[PF069], [PF091], [PF171]]From Singularity Analysis (Vol I): [[PF086], [PF148]]From ? Chapter 3 (Vol I): [[PF190]]From Gaussian Limit Laws (Vol II): [[PF159]]3
4DR FLAJOLET’S ELIXIR OR MELLIN TRANSFORM AND ASYMPTOTICSFrom Airy Function (Vol II): [[PF160]]From Divide & Conquer and the Mellin-Perron Formula (Vol III) [[PF115], [PF116]]From Protocols (Vol III): [[PF054], [PF055], [PF071]]From Height of trees (Vol IV): [[PF033], [PF206]]From Number Theory (Vol V): [[PF143], [PF197]]From Register Function (Vol V): [[PF017], [PF020], [PF027], [PF057]]From Computer Algebra (Vol VI): [[PF207]]From Automatic Analysis (Vol VI): [[PF094]]From Approx. Counting (Vol VI): [[PF050], [PF084], [PF193]]Philippe Flajolet (abbreviated PF in the sequel) greatly developed the use ofMellin transform in the asymptotic evaluation of some combinatorial sums that appear in the average case analysis of algorithms. In fact, the Mellin transform runsthroughout PF’s work from the beginning [PF033] to the very end [PF206].Mellin transform and fundamental stripThe Mellin transform is an integral transform, like the Laplace transform or theFourier transform. It takes as input the original f (x), which is a function of a realvariable defined on the real positive half-line. It produces the image f (s), which is afunction of a complex variable, defined byZ 1f (s) f (x)xs 1 dx.0It is not clear that the formula actually defines anything, but the kernel xs 1 leadsus to a comparison with the powers of x. It is readily seen that the assumptionf (x) x!0 O(x ) guarantees the convergence of the lower part of the integral, sayfrom 0 to 1, for complex numbers s whose real part is greater than , that is for thes which are on the right of . We can make a similar assumption about the behaviorat infinity. In this way, the image f (s) is defined within the intersection of a righthalf-plane and a left half-plane. This is a strip, called the fundamental strip.Certainly the most basic example of a Mellin transform is the gamma functionZ 1e x xs 1 dx.(s) 0It is the Mellin transform of the exponential e x . In that case the original is O(1) at 0,so the left abscissa of the fundamental strip is 0. It decreases as x tends to infinity morerapidly than every power of x and the right abscissa is 1. Hence the fundamentalstrip in this case is the positive right half-plane. But the gamma function extends tothe whole complex plane as a meromorphic function, and the extension has poles atall the nonpositive integers. The extension has poles at all the nonpositive integers,hence the peaks on the left-hand side of Figure 1.
SYMBOLIC ANALYSIS5Figure 0.1. Absolute value of the gamma function.Symbolic analysisImagine a flat landscape, something like a flat sand desert. This country is thecomplex plane. A track straight through it. This is the real axis. But you are thinkingof a meromorphic function and suddenly this changes the landscape. Some hills oreven prodigious mountains appear and at the top of these mountains some placardsare fixed on poles. Each vertex is located above a pole of the meromorphic function and on the placard you can read the singular part of the function at the pole.For example, if you are thinking of the gamma function, you see an infinity of chimneys aligned on the negative part of the real axis, which disappear at the horizon ina haze of heat. On the placard at abscissa k, you read ( 1)k /(x k). Your fantasy knows no limits and if you thought only for a moment about Stirling’s formula aplacard appears on thepother side, at the end of the real positive axis, with its wordingx(x) x! 1 (x/e)2 /x. The more you direct your gaze toward a part of thelandscape, the more details spring up.There is no doubt that PF had such a mental image of analytic functions, certainlyin a more subtle way, refined by more than thirty years of practice. Undisputable evidences are the introduction to the saddle-point method of [PF201, Chap. VIII], thediscussion about coalescing saddle-points from [PF160], or the picture of [PF207]illustrating the application of the saddle-point method to a generalized exponentialintegral. Similarly, the search for summatory formulas is reduced to a purely formalhandling [PF143]; the asymptotic study of divide-and-conquer type sums is reduced
6DR FLAJOLET’S ELIXIR OR MELLIN TRANSFORM AND ASYMPTOTICSDe Bruijn, 1948 1Xk 0De Bruijn, Knuth,Rice, 1972Knuth, 1973XXkb d(k)exr kpx 1/ nk2 x2j (ex/2j1 x/2j )x n1Xk 1XKemp, 19791e1k 1jSedgewick, 1978lnr F (k)eka v2 (2k)ek2 xpx 1/ j16k2 xpx 1/ nk 1TABLE 1. The first uses of the Mellin transform approach related to theanalysis of algorithms, with their authors and date, and the harmonics sumstherein.to picking residues [PF115; PF116]. Always he was defining rules that provide an automatic treatment of issues and reduce mathematical analysis to algebra and rewritingsystems [PF094; PF171]. Here we try to mimic this attitude and concentrate on theideas, neglecting the mathematical assumptions.Fundamental resultThe fundamental result about Mellin transform is the following. There is a strongcorrespondence between the behavior of the original at 0 and the poles of the imagein the left half-plane with respect to the fundamental strip. Similarly, the behaviorat infinity of f (x) is related to the poles of f (s) in the half-plane to the right ofthe fundamental strip. The correspondence is explicit and given by the followingformulas: a term x lnk x in the expansion at 0 corresponds exactly to a singular term( 1)k k!/(s )k for a pole at the left of the fundamental strip. The formula isthe same for the expansion at 1 and the poles on the right-hand side of the strip, butwith an opposite sign: to ( 1)k k!/(s )k corresponds x lnk x. Particularly, forsimple poles (that is k 0), it is very simple: on the left-hand side the coefficients ofthe expansion at 0 are the residues of the poles, and similarly on the right-hand side.Clearly, the correspondence works very well in case of the gamma function,(1)(s) 1X( 1)k 1,k! s kRe(s) 0 k 0ex 1X( 1)k kx .x!0k! k 0Note that in (1) we do not claim that the series converges or even that the sum isthe gamma function. This equation is only a formal writing, in line with symbolicanalysis.
ZIGZAG METHOD7Harmonic sumsThe second component of the story is the notion of harmonic sum. We start with abase function and its Mellin transform. To the base function, we associate a harmonicsumX(2)F (x) k f ( k x).kThis is a linear combination of some dilations of the base function. We merge bothideas and we obtain a very simple result about the Mellin transform F (s) of theharmonic sum. It is the product of the Mellin transform f (s) of the base functionand some generalized Dirichlet series (s), which depends only on the coefficientsinvolved in the harmonic sum,X k(3)F (s) f (s).µskkZigzag methodWe understand the power of the previous results by playing with the zigzagmethod, going back and forth between originals and images. We start with our favoriteexample f1 (x) e x and its Mellin transform, the gamma function. We consider analternative function 1Xxf2 (x) x xe kx ,e1k 1which is actually a harmonic sum. We compute its Mellin transform and we collect itspoles 1f2 (s) (s 1) (s 1)1 X ( 1)j ( j)1 .j!s j 1Re(s) 0 sj 0 They are 0 and the negative integers. But we know thatf2 (x) 1 1X1B2k 2kx x2(2k)!n 1is the generating function of the Bernoulli numbers. Moreover these numbers are zerofor odd integers starting at 3, hence the writingf2 (s)1Re(s) 0 s 1X B2k1 11 .2s 1(2k)! s 2kk 1As a consequence the zeta function vanishes for the negative even integers. We nowbring into the game a new harmonic sumX2 2f3 (x) e k xk 1
8DR FLAJOLET’S ELIXIR OR MELLIN TRANSFORM AND ASYMPTOTICSand compute its Mellin transform1 s (s).22The vanishing of zeta at all the even negative integers removes almost all the poles ofthe gamma function. There remain only two poles, at 0 and 1. Withp 111 f3 (s) 1 2sRe(s) 1 2 sf3 (s) (again, the writing is purely formal), we readily obtain the expansion of the functionat 0p 1 1f3 (x) O(x 1 ).x!0 2 x2Once we have understood the trick, it is not difficult to deal with other examples, likeX2 2f4 (x) d(k)e k x .k 1Here, d is the divisor function and the Mellin transform is f4 (s) (s/2) (s)2 /2.Again we obtain the expansion at 0 easily (the double pole at 1 makes a logarithmarise)pp ln x 1 1f4 (x) (3ln 4) O(x 1 ).x!0 2x4x 4Average-case analysis of algorithms and harmonic sumsThe application of the previous ideas to the analysis of algorithms began in theseventies, with a 1972 article [BKR72] of Nicolaas G. De Bruijn, Donald E. Knuth,and Stephen O. Rice about the height of rooted plane trees (Table 1). Knuth [Knu73,p. 132-124] refers to the method of the gamma function and credits De Bruijn withfirst having this idea. De Bruijn had used it in a 1948 paper [DB48] about the asymptotic evaluation of the binary partitions number. Next we encounter the studyof radix-exchange sorting by Donald Knuth [Knu73], of the odd-even merging byRobert Sedgewick [Sed78b], and of the register allocation for binary trees by RainerKemp [Kem78]. In every case, a harmonic sum comes out (in the expressions of Table 1, d is the divisor function, r andare the backward and forward differenceoperators, v2 is the dyadic valuation function). The first sum is a generating function,while the others ones are combinatorial sums, but they are all amenable to the sametreatment.According to [PF190], PF learned the Mellin transform from Rainer Kemp around1979. In a 1977 work about register allocation [PF013; PF020], PF and his coauthors follow an elementary way à la Delange, but in a 1978/1979 talk [PF017] at theSéminaire Delange-Pisot-Poitou PF gives an explanation about the “Mellin-Fouriertransform”, with only words but in a totally clear way. PF has systematized the ideastarting in the eighties and completely defined the method in the early nineties. Thisled him to write first [PF052], a very illuminating presentation of the Mellin transformin the context of the analysis of algorithms, and next [PF120], a more comprehensive
EXPONENTIALS IN HARMONIC SUMSPF, Odlyzko, 1981[RR0056; PF033]average height ofsimple treesPF, Puech, 1983[RR0233; PF058]retrieval of multidimensional dataFayolle, PF, Hofri,1986 [RR0131;PF055]multi-accessbroadcast channelPF, Richmond,1992 [RR1423;PF101]generalizeddigital treesMahmoud, PF,Jacquet, Régnier,2000 [RR3399;PF159]bucket selectionand sortingPF, Fusy,Gandouet,Meunier, 2007[PF193]cardinalityestimationBroutin, PF, 2010[PF206]height innon-planebinary treesXr (n)e9nun 1kX1" XXj2j(ks)0(1e x i,jj, ex j, )µ( (1 Kµ) 2H(e rx 1 rx) Krx(e rx 1) ) 1X k (1 2k t)b 12,Q(2k t)b 1k 0Y u Q(u) 1 j2j 0ze 1X(1ez/B k) and relativesk 0 1X(ex/2ke2x/2k)exu/2kk 1Xh 1hre(1hteht )2TABLE 2. Some of PF’s contributions with their authors, date, and references, next the topics under consideration, and finally the harmonic sums thatappear in these papers.version. He returned to the topic in [PF129], in which the reader can find not onlyexamples but even exercises.Table 2 provides a small sample of PF’s contributions. The third example [RR0131;PF055] is impressive: the sum is over the affine transforms (z) µ rz in asemi-group H { 1 , 2 } generated by two affine transforms 1 (z) pz, qz with p q 1. The scope of application is quite broad and we refer2 (z) to [PF120, p. 5] for a list of relevant fields.Exponentials in harmonic sumsIt is remarkable how often the exponential function appears in the harmonic sums.The reason is the following. In the process of analyzing an algorithm, we are facedwith combinatorial sums, which generally are not harmonic sums. But there may be asuitable approximation which is a harmonic sum. There are essentially two rules. The
10DR FLAJOLET’S ELIXIR OR MELLIN TRANSFORM AND ASYMPTOTICSfirst is the approximation of a large power by an exponential,(1a)n n! 1ena1 O(na2 )with na n! 1n" ,0 " 1/2Here is an example related to the analysis of the radix-exchange sort algorithm [Knu73,p. 131] n 1 1XXk11p11 F (n) O,F (x) (1 e x/2 ).n! 12knk 0k 0Others examples can be found in [PF050, p.188], [PF058, p. 230], [PF086, p. 388],[PF206, p.131], or [PF197, p. 71].The second rule is the approximation of the binomial distribution by a Gaussiandistribution 2n p21n k e w 1 Owith k w n, k o(n3/4 ).n! 1n! 12nnnIt appears in the study of the expected height of plane (Catalan) trees [BKR72, p. 20] 2n n 1XX2 21n kd(k) G p o(1)G(x) d(k)e k x .n! 12nnk 1k 1nor in the study of odd-even merging [Sed78b], [PF027, p. 153] resumed in [PF069,p. 286] and [PF091, p. 478].Technical pointFor the benefit of the reader who wants to apply the Mellin transform to his/herown problem, we leave for a while the formal style and enter into analysis. Frequently,the original f (x) is not only defined on the real positive axis, but on a sector arg x ! of the complex plane. This constraints the image strongly. In this case, it satisfies(4) f (s) s! i1e! Im(s) .Such an inequality (not necessarily of exponential type) is the key point allowing touse the inverse formulaZ1(5)f (x) f (s)x s ds2 i (c)(see the proof of Theorem 4 in [PF120]). In this formula, (c) is the vertical line at abscissa c taken in the fundamental strip. It is noteworthy that x can be a complex variable and not only a positive real variable, contrary to what we started with ([Doe55] or[JS98] for a brief account). This is of practical importance since the application of theMellin transform to a generating function is frequently the first step of an analyticalprocess. It provides the local behaviour of the function at a distinguished point, andcan be followed by the use of the Cauchy formula, for example with the saddle-point
OSCILLATIONS11Figure 0.2.The Mellin transform captures oscillating behavior of a verysmall amplitude.method [DB48; PF125], or followed by singularity analysis [PF084, p. 397], [PF086,p. 238], [PF206, p. 24].OscillationsThe study of the number of registers necessary to evaluate an expression represented by a binary tree is perhaps the most classical example which provides a harmonic sum. PF and Helmut Prodinger dealt with a variant of the problem in a 1986paper [PF057]. They begin by revisiting the case of a binary tree. They need to knowthe local behaviour of the function1 u2 XE(z) v2 (k)ukuk 1in the neighborhood of 1/4. For this, they perform some changes of variablesz u,(1 u)2u 1 r,1 rr p14z,u et(z 1/4 corresponds to u 1 and t 0) and a harmonic sum V (t) comes out. Theythen compute its Mellin transform,X (s)V (t) v2 (k)e kt ,V (s) s (s).21k 1
12DR FLAJOLET’S ELIXIR OR MELLIN TRANSFORM AND ASYMPTOTICSThey collect the coefficients of the asymptotic expansion of V (t) at 0 by a processwhich seems now to be routine. Because of the denominator 2s 1, there is a line ofpoles k 2k i/ ln 2 on the imaginary axis. These poles are regularly spaced andcontribute a trigonometric series C P (log2 t) with respect to log2 t,X ( k ) ( k )1ln(2 )C ,P (log2 t) e 2k i log2 (t) .42 ln 2ln 2k6 0In this way they obtain the expansion they are looking for11V (t) ln(t) C P (log2 t) O(t),t!0 t2 ln 2pE(z) 2 2r log2 r (2C 1)r 4rP (log2 r) O(r2 ),r 1z!1/44z.The key point is the occurrence of a function which is 1-periodic with respect tolog2 t. The gamma function decreases very rapidly on the imaginary axis and thisperiodic function therefore has a very small amplitude. (Figure 2 displays the graphof P (log2 t)). More precisely, the magnitudes are C ' 0.66, ( 1 ) ' 5.5 10 7 , ( 2 ) ' 2.5 10 13 , ( 3 ) ' 1.4 10 19 . . . One could say that this function is sosmall as to be of no importance. But it emphasizes the difficulty to obtain such anasymptotic expansion by elementary arguments. This point in particular delighted PF[PF054, Comment 5, p. 226], [PF071, p. 8], [PF050, p. 206].Related topicsIn this small introduction to the Mellin transform, we have neglected many issues.Among them, the Rice formula permits to study high order differences of a sequence.Also, the Poisson-Mellin-Newton cycle relates the Poisson generating function of asequence, its Mellin transform, and the Rice integral. A good reference about thesetopics is PF and Robert Sedgewick’s 1995 article [PF124]. Another topic omitted hereis the Mellin-Perron formula. It is presented in the next chapter of this volume. Mellintransform is a pivotal ingredient in depoissonization [JS98; PF193]. It is also relatedwith the Lindelöf representation, which appears in [PF148, Formula (11)], [PF171,p. 565], itself connected with the magic duality. PF often spoke about this topic, buthe has written very little about it. It is alluded to in [PF207] and developed brieflyin a note of Analytic combinatorics [PF201, p. 238]. The right reference is [Lin89,Chap. V].
3][KP84][KP87][Lin89][PF013][PF017]N. G. de Bruijn, D. E. Knuth, and S. O. Rice. “The average height ofplanted plane trees”. In: Graph theory and computing. New York: Academic Press, 1972, pp. 15–22.N. G. De Bruijn. “On Mahler’s partition problem”. In: Indagationes Mathematicae 10 (1948). Reprinted from Koninklijke Nederlandsche Akademievan Wetenschappen, Ser. A, pp. 210–220.Gustav Doetsch. Handbuch der Laplace Transformation, Vol. 1–3. Basel:Birkhäuser Verlag, 1955.Philippe Jacquet and Wojciech Szpankowski. “Analytical Depoissonization and its Applications”. In: Theor. Comput. Sci. 201.1-2 (1998), pp. 1–62.R. Kemp. “The average number of registers needed to evaluate a binary tree optimally”. In: Acta Inform. 11.4 (1978/79), pp. 363–372. ISSN:0001-5903. DOI: 10.1007/BF00289094. URL: http://dx.doi.org/10.1007/BF00289094.Donald E. Knuth. The art of computer programming. Volume 3. Sorting and searching, Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading, Mass.London-Don Mills, Ont., 1973, xi 722 pp. (1 foldout).Peter Kirschenhofer and Helmut Prodinger. “Recursion depth analysis forspecial tree traversal algorithms”. In: Automata, languages and programming (Antwerp, 1984). Vol. 172. Lecture Notes in Comput. Sci. Berlin:Springer, 1984, pp. 303–311.Peter Kirschenhofer and Helmut Prodinger. “On the recursion depth ofspecial tree traversal algorithms”. In: Inform. and Comput. 74.1 (1987),pp. 15–32. ISSN: 0890-5401.Ernst Lindelöf. Le calcul des résidus et ses applications à la théoriedes fonctions. Les Grands Classiques Gauthier-Villars. [Gauthier-VillarsGreat Classics]. Reprint of the 1905 original. Sceaux: Éditions JacquesGabay, 1989, pp. viii 145. ISBN: 2-87647-060-8.Philippe Flajolet, Jean-Claude Raoult, and Jean Vuillemin. “On the average number of registers required for evaluating arithmetic expressions”.In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1977, pp. 196–205.Philippe Flajolet. “Deux problèmes d’analyse d’algorithmes”. In: Séminaire Delange-Pisot-Poitou (Théorie des Nombres) 20 (1978/79), 14–01–14–10.13
BIBLIOGRAPHYPhilippe Flajolet, Jean-Claude Raoult, and Jean Vuillemin. “The numberof registers required for evaluating arithmetic expressions”. In: Theoretical Computer Science 9 (1979), pp. 99–125.Philippe Flajolet and Lyle Ramshaw. “A Note on Gray Code and OddEven Merge”. In: SIAM Journal on Computing 9 (1980), pp. 142–158.Philippe Flajolet and Andrew Odlyzko. “The average height of binarytrees and other simple trees”. In: Journal of Computer and System Sciences 25 (1982), pp. 171–213.Philippe Flajolet and G. Nigel Martin. “Probabilistic counting algorithmsfor data base applications”. In: Journal of Computer and System Sciences31 (1985), pp. 182–209.Philippe Flajolet, Mireille Régnier, and Robert Sedgewick. “Some usesof the Mellin integral transform in the analysis of algorithms”. In: Combinatorial Algorithms on Words. Ed. by Alberto Apostolico and Zvi Galil.Vol. 12. NATO Advance Science Institute Series, Series F: Computer andSystems Sciences. Proceedings of the NATO Advanced Research Workshop on Combinatorial Algorithms on Words held at Maratea, Italy. Berlin/Heidelberg:Springer-Verlag, 1985, pp. 241–254.Peter Mathys and Philippe Flajolet. “Q-ary collision resolution algorithmsin random-access systems with free or blocked channel access”. In: IEEETransactions on Information Theory IT-31 (1985), pp. 217–243.Guy Fayolle, Philippe Flajolet, and Micha Hofri. “On a Functional Equation Arising in the Analysis of a Protocol for a Multi-Access BroadcastChannel”. In: Advances in Applied Probability 18 (1986), pp. 441–472.Philippe Flajolet and Helmut Prodinger. “Register Allocation for UnaryBinary Trees”. In: SIAM Journal on Computing 15 (1986), pp. 629–640.Philippe Flajolet and Claude Puech. “Partial match retrieval of multidimensional data”. In: Journal of the ACM 33 (1986), pp. 371–407.Philippe Flajolet. “Mathematical methods in the analysis of algorithmsand data structures”. In: Trends in Theoretical Computer Science. Ed. byEgon Börger. Volume 12 in the series “Principles of computer science;”Lecture Notes from 1984 for A Graduate Course in Computation Theory, Udine, Italy. Rockville, Maryland: Computer Science Press, 1988.Chap. 6, pp. 225–304.Philippe Flajolet. Évaluation de protocoles de communication : aspectsmathématiques. Research Report 797. 22 pages. Main lecture deliveredat the Journée annuelle de la Société Mathématique de France, Paris,January 1988. Institut National de Recherche en Informatique et en Automatique (INRIA), 1988.Philippe Flajolet. “On adaptive sampling”. In: Computing 43 (1990). Thearticle has volume 34 printed at the top, but it is actually contained involume 43., pp. 391–400.Philippe Flajolet and Andrew Odlyzko. “Singularity Analysis of Generating Functions”. In: SIAM Journal on Discrete Mathematics 3 (1990),pp. 216–240.Jeffrey Scott Vitter and Philippe Flajolet. “Average-Case Analysis of Algorithms and Data Structures”. In: Handbook of Theoretical ComputerScience. Ed. by Jan van Leeuwen. Vol. A: Algorithms and Complexity.Amsterdam: North-Holland, 1990. Chap. 9, pp. 431–524.
71][PF190][PF193][PF197][PF201]15Philippe Flajolet, Bruno Salvy, and Paul Zimmermann. “Automatic averagecase analysis of algorithms”. In: Theoretical Computer Science 79 (1991),pp. 37–109.Philippe Flajolet and Bruce Richmond. “Generalized Digital Trees andTheir Difference-Differential Equations”. In: Random Structures & Algorithms 3 (1992), pp. 305–320.Philippe Flajolet and Mordecai Golin. “Mellin Transforms and Asymptotics: The Mergesort Recurrence”. In: Acta Informatica 31 (1994), pp. 673–696.Philippe Flajolet et al. “Mellin transforms and asymptotics: digital sums”.In: Theoretical Computer Science 123 (1994), pp. 291–314.Philippe Flajolet, Xavier Gourdon, and Philippe Dumas. “Mellin transforms and asymptotics: Harmonic sums”. In: Theoretical Computer Science 144 (1995), pp. 3–58.Philippe Flajolet and Robert Sedgewick. “Mellin transforms and asymptotics: Finite differences and Rice’s integrals”. In: Theoretical ComputerScience 144 (1995), pp. 101–124.Philippe Dumas and Philippe Flajolet. “Asymptotique des récurrencesmahlériennes : le cas cyclotomique”. In: Journal de Théorie des Nombres de Bordeaux 8 (1996), pp. 1–30.Philippe Flajolet and Robert Sedgewick. The Average Case Analysis ofAlgorithms: Mellin Transform Asymptotics. Research Report 2956. 93 pages.Institut National de Recherche en Informatique et en Automatique (INRIA), 1996.Philippe Flajolet and Bruno Salvy. “Euler Sums and Contour IntegralRepresentations”. In: Experimental Mathematics 7 (1998), pp. 15–35.Philippe Flajolet. “Singularity analysis and asymptotics of Bernoulli sums”.In: Theoretical Computer Science 215 (1999), pp. 371–381.Hosam Mahmoud et al. “Analytic variations on bucket selection and sorting”. In: Acta Informatica 36 (2000), pp. 735–760.Cyril Banderier et al. “Random maps, coalescing saddles, singularity analysis, and Airy phenomena”. In: Random Structures & Algorithms 19 (2001),pp. 194–246.Philippe Flajolet. “Singular Combinatorics”. In: Proceedings of the International Congress of Mathematicians (ICM-2002). Ed. by Li Tatsien.Vol. III. Beijing, China: World Scientific, 2002, pp. 561–571.Philippe Flajolet, Markus Nebel, and Helmut Prodinger. “The scientificworks of Rainer Kemp (1949–2004)”. In: Theoretical Computer Science355 (2006), pp. 371–381.Philippe Flajolet et al. “HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm”. In: Proceedings of the 2007 Conferenceon Analysis of Algorithms (AofA ’07). Ed. by Philippe Jacquet. Vol. AH.DMTCS Proceedings. 2007, pp. 127–146.Philippe Flajolet and Linas Vepstas. “On differences of zeta values”. In:Journal of Computational and Applied Mathematics 220 (2008), pp. 58–73.Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. xiv 810 pages.Also available electronically from the authors’ home pages. CambridgeUniversity Press, 2009.
R3399][Sed78a][Sed78b]BIBLIOGRAPHYNicolas Broutin and Philippe Flajolet. “The distribution of height and diameter in random non-plane binary trees”. To appear; arXiv:1009.1515v2,arXiv. 34 pages. 2011.Philippe Flajolet, Stefan Gerhold, and Bruno Salvy. “Lindelöf representations and (non-)holonomic sequences”. In: Electronic Journal of Combinatorics 17.#R3 (2010), pp. 1–28.Philippe Flajolet and Andrew Odlyzko. The average height of binary treesand other simple trees. Research Report. 55 pages. Institut National deRecherche en Informatique et en Automatique (INRIA), 1981.Guy Fayolle, Philippe Flajolet, and Micha Hofri. On a Functional Equation Arising in the Analysis of a Protocol for a Multi-Access BroadcastChannel. Research Report 131. 36 pages. Institut National de Rechercheen Informatique et en Automatique (INRIA), 1982.Philippe Flajolet and Claude Puech. Partial match retrieval of multidimensional data. Research Report 233. 45 pages. Institut National de Rechercheen Informatique et en Automatique (INRIA), 1983.Philippe Flajolet and Bruce Richmond. Generalized Digital Trees andTheir Difference-Differential Equations. Research Report 1423. 15 pages.Institut National de Recherche en Informatique et en Automatique (INRIA), 1991.Hosam Mahmoud et al. Analytic variations on bucket selection and sorting. Research Report 3399. 22 pages. Institut National de Recherche enInformatique et en Automatique (INRIA), 1998.Robert Sedgewick. “Data movement in odd-even merging”. In: Proceedings of a Conference on Theoretical Computer Science (Univ. Waterloo,Waterloo, Ont., 1977). Comput. Sci. Dept., Univ. Waterloo, Waterloo,Ont., 1978, pp. 163–172.Robert Sedgewick. “Data movement in odd-even merging”. In: SIAM J.Comput. 7.3 (1978), pp. 239–272. ISSN: 0097-5397.
pear in the average case analysis of algorithms. In fact, the Mellin transform runs throughout PF's work from the beginning [PF033] to the very end [PF206]. Mellin transform and fundamental strip The Mellin transform is an integral transform, like the Laplace transform or the Fourier transform.
