HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal.inria.fr/inria-00073742
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:39:37 PM
Last modification on : Friday, February 4, 2022 - 3:08:13 AM
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

77

Files downloads

246