PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1: Complexity Analysis of String Algorithms


St. Petersburg - Sunday, March 28 through Wednesday, April 7, 2004

Ilja Posov

Mellin transforms and asymptotics: Harmonic sums


Abstract

This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models, and the average-case analysis of algorithms. It relies on the Mellin transform, a close relative of the integral transforms of Laplace and Fourier. The method applies to harmonic sums that are superpositions of rather arbitrary "harmonics" of a common base function. Its principle is a precise correspondence between individual terms in the asymptotic expansion of an original function and singularities of the transformed function. Here no theorem is proved, and even not every theorem is completely formulated. For precise presentation of the theory reader is refered to the original paper.


Presentation:
11 Posov Ilya The Mellin transform.ppt
11 Posov Ilya The Mellin transform.pdf
Paper:
Chapter 11 (Postscript PS, PDF PDF) of the proceedings (Postscript PS, PDF PDF).