Mellin transforms and asymptotics: the mergesort recurrence

Philippe Flajolet 1 Mordecai Golin 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : 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-case. 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.
Type de document :
Rapport
[Research Report] RR-1612, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074948
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 17:02:44
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : mardi 12 avril 2011 - 20:14:45

Fichiers

Identifiants

  • HAL Id : inria-00074948, version 1

Collections

Citation

Philippe Flajolet, Mordecai Golin. Mellin transforms and asymptotics: the mergesort recurrence. [Research Report] RR-1612, INRIA. 1992. 〈inria-00074948〉

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

74