HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >

Please use this identifier to cite or link to this item:
Title: Mellin transforms and asymptotics : the mergesort recurrence
Authors: Flajolet, Philippe
Golin, Mordecai J.
Keywords: Mellin transforms
Dirichlet series
Recursive mergesort algorithm
Gaussian limiting distribution
Divide-and-conquer recurrences
Issue Date: 1993
Citation: Acta informatica, v. 31, 1994, p. 673-696
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 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.
Appears in Collections:CSE Preprints

Files in This Item:

File Description SizeFormat
MergeAv.pdf301KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.