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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00074948
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 5:02:44 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Tuesday, April 12, 2011 - 8:14:45 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

204

Files downloads

101