Mellin transforms and asymptotics: the mergesort recurrence - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1992

Mellin transforms and asymptotics: the mergesort recurrence

Philippe Flajolet
  • Fonction : Auteur
  • PersonId : 829512
Mordecai Golin
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1612.pdf (601.09 Ko) Télécharger le fichier

Dates et versions

inria-00074948 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074948 , version 1

Citer

Philippe Flajolet, Mordecai Golin. Mellin transforms and asymptotics: the mergesort recurrence. [Research Report] RR-1612, INRIA. 1992. ⟨inria-00074948⟩
139 Consultations
82 Téléchargements

Partager

Gmail Facebook X LinkedIn More