Title: Philippe Flajolet, Divide & Conquer Recurrences and The Mellin-Perron Formula

Speaker: Mordecai Golin, HKUST

Time/Date:  Friday, Mar 2, 11-12
Location: Room 3464

Abstract: Most computer scientists know of the Master Theorem" for Divide & Conquer Recurrences.
These recurrences are ubiquitous in Computer Science, describing the running time, space usage,
work, etc. of many fundamental algorithms.   The Master Theorem provides a quick way of deriving 
first order asymptotics of the solution to such recurrences.

Very often, the solutions to Divide & Conquer recurrences contain periodic terms; sometimes
as coefficients of first order asymptotics, sometimes as coefficients of lower order terms. Standard
tools for analyzing these recurrences, such as the Master Theorem, often miss these terms.
In this talk we describe a general technique developed and popularized by Philippe Flajolet for
solving these and related functions.  This technique easily derives the periodic terms. It is based on
the Mellin-Perron formula, one of the galaxy of methods related to Mellin
transform analysis. As in many Mellin transform analysis based techniques, the final step of the
method transforms the problem into the calculation of the singularities of appropriate functions.

This talk is an introduction to the use of tools from analytic combinatorics to the analysis of
algorithms.  It is self-contained, and no previous knowledge of algorithmic theory or
complex analysis is assumed.

Note: This talk is an extended version of one that was given this past December in Paris at the
Conference in the memory of Philippe Flajolet: Philippe Flajolet and Analytic Combinatorics