The Average Case Analysis of Algorithms: Mellin Transform Asymptotics

Philippe Flajolet 1 Robert Sedgewick
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It reviews the use of Mellin-Perron formulæand of Mellin transforms in this context. Applications include: divide-and-conquer recurrences, maxima finding, mergesort, digital trees and plane trees.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073742
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:39:37 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Monday, September 17, 2012 - 2:45:08 PM

Identifiers

  • HAL Id : inria-00073742, version 1

Collections

Citation

Philippe Flajolet, Robert Sedgewick. The Average Case Analysis of Algorithms: Mellin Transform Asymptotics. [Research Report] RR-2956, INRIA. 1996. ⟨inria-00073742⟩

Share

Metrics

Record views

139

Files downloads

431