×

Mellin transforms and asymptotics. The mergesort recurrence. (English) Zbl 0818.68064

Summary: Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise analysis of the standard top-down recursive mergesort algorithm, in the average case, as well as in the worst and best cases. It also derives the variance and shows that the cost of mergesort has a Gaussian limiting distribution. The approach is applicable to a number of divide-and-conquer recurrences.

MSC:

68P10 Searching and sorting
44A15 Special integral transforms (Legendre, Hilbert, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P.: Automates finis en théorie des nombres. Expo. Math.5, 239-266, (1987) · Zbl 0641.10041
[2] Allouche, J.-P., Cohen, H.: Dirichlet series and curious infinite products. Bull. Lond. Math. Soc.17, 531-538 (1985) · Zbl 0577.10036 · doi:10.1112/blms/17.6.531
[3] Allouche, J.-P., Shallit, J.: The ring ofk-regular sequences. Theor. Comput. Sci.98, 163-197 (1992) · Zbl 0774.68072 · doi:10.1016/0304-3975(92)90001-V
[4] Apostol, T.M.: Introduction to analytic number theory. Berlin, Heidelberg, New York: Springer 1976 · Zbl 0335.10001
[5] Billingsley, P.: Probability and measure, 2nd edn. New York: John Wiley 1986 · Zbl 0649.60001
[6] Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms. New York: MIT Press 1990 · Zbl 1158.68538
[7] Delange, H.: Sur la fonction sommatoire de la fonction somme des chiffres. Enseign. Math.21 (1), 31-47 (1975) · Zbl 0306.10005
[8] Dumas, P.: Critères de B-régularité. Cah. Sémin. Théorie Nombres (Bordeaux) (1994, to appear)
[9] Dumont, J.-M., Thomas, A.: Systèmes de numération et fonctions fractales relatifs aux substitutions. Theor. Comput. Sci.65, 153-169 (1989) · Zbl 0679.10010 · doi:10.1016/0304-3975(89)90041-8
[10] Flajolet, P., Golin, M.: Exact asymptotics of divide-and-conquer recurrences. In: Lingas, S.C.A., Karlsson, R. (eds.) Automata, languages, and programming (Lect. Notes Comput. Sci., vol. 700, pp. 137-149) Berlin, Heidelberg, New York: Springer 1993
[11] Flajolet, P., Grabner, P., Kirschenhofer, P., Prodinger, H., Tichy, R.: Mellin transforms and asymptotics: Digital sums. Theor. Comput. Sci.123, 291-314 (1994) · Zbl 0788.44004 · doi:10.1016/0304-3975(92)00065-Y
[12] Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci.31 (2), 182-209 (1985) · Zbl 0583.68059 · doi:10.1016/0022-0000(85)90041-8
[13] Knuth, D.E.: The art of comput4r programming, vol. 3: Fundamental algorithms, 2nd edn. Reading, MA: Addison-Wesley 1968 · Zbl 0191.17903
[14] Knuth, D.E.: The art of computer programming, vol. 3: Sorting and searching. Reading, MA: Addison-Wesley 1973 · Zbl 0302.68010
[15] Sedgwick, R.: Algorithms, 2nd edn. Reading, MA: Addison-Wesley 1988
[16] Stolarsky, K.B.: Power and exponential sums of digital sums related to binomial coefficients. SIAM J. Appl. Math.32 (4) 717-730 (1977) · Zbl 0355.10012 · doi:10.1137/0132060
[17] Vardi, I.: Computational recreations in mathematica. Reading, MA: Addison Wesley 1991 · Zbl 0786.11002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.