Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/469

MELLIN TRANSFORMS AND ASYMPTOTICS - THE MERGESORT RECURRENCE

Authors FLAJOLET, P
GOLIN, M
Issue Date 1994
Source Acta Informatica, v. 31, (7), 1994, OCT, p. 673-696
Summary Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer. 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.
Subjects
ISSN 0001-5903
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
MergeAv.pdf 308343 B Adobe PDF