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|
Recursive mergesort algorithm
Gaussian limiting distribution
|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:
All items in this Repository are protected by copyright, with all rights reserved.