Mellin transforms and asymptotics. The mergesort recurrence

DOI10.1007/BF01177551zbMath0818.68064OpenAlexW2913954881MaRDI QIDQ1338908

Philippe Flajolet, Mordecai J. Golin

Publication date: 18 December 1994

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01177551

zbMATH Keywords

Dirichlet seriesMellin transformsdivide-and-conquer algorithmsmergesort algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Special integral transforms (Legendre, Hilbert, etc.) (44A15)

Related Items

Bottom-up mergesort -- A detailed analysis, Asymptotics of Mahler recurrences: The cyclotomic case, Asymptotic expansion for the Lebesgue constants of the Walsh system, Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated, A More Malicious Maitre d’, Unnamed Item, Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences, An asymptotic theory for recurrence relations based on minimization and maximization., Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, Digital search trees with keys of variable length, Distribution of the sum-of-digits function of random integers: a survey, A general limit theorem for recursive algorithms and combinatorial structures, On tries, contention trees and their analysis, Exact asymptotics of divide-and-conquer recurrences, Algebraic aspects of B-regular series, Mellin transforms and asymptotics: Harmonic sums, The complexity space of partial functions: a connection between complexity analysis and denotational semantics, Singularity analysis, Hadamard products, and tree recurrences, Analytic analysis of algorithms, QuickXsort: a fast sorting scheme in theory and practice, Presorting algorithms: an average-case point of view, Mellin transforms and asymptotics: Digital sums

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic counting algorithms for data base applications
• Finite automata in number theory
• Systèmes de numération et fonctions fractales relatifs aux substitutions. (Numeration systems and fractal functions related to substitutions)
• The ring of \(k\)-regular sequences
• Sur la fonction sommatoire de la fonction 'somme des chiffres'
• Mellin transforms and asymptotics: Digital sums
• Dirichlet Series and Curious infinite Products
• Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity