Mellin transforms and asymptotics: Finite differences and Rice's integrals

Philippe Flajolet; Robert Sedgewick

doi:10.1016/0304-3975(94)00281-M

Mellin transforms and asymptotics: Finite differences and Rice's integrals

Philippe Flajolet
, Robert Sedgewick

Computer Science

Research output: Contribution to journal › Article › peer-review

173 Scopus citations

Abstract

High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin transform asymptotics, is put in perspective and illustrated by means of several examples related to combinatorics and the analysis of algorithms like digital tries, digital search trees, quadtrees, and distributed leader election.

Original language	English (US)
Pages (from-to)	101-124
Number of pages	24
Journal	Theoretical Computer Science
Volume	144
Issue number	1-2
DOIs	https://doi.org/10.1016/0304-3975(94)00281-M
State	Published - Jun 26 1995

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(94)00281-M

Cite this

@article{bdbf9dd072774bfbb43d82bb0d3015f7,

title = "Mellin transforms and asymptotics: Finite differences and Rice's integrals",

abstract = "High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin transform asymptotics, is put in perspective and illustrated by means of several examples related to combinatorics and the analysis of algorithms like digital tries, digital search trees, quadtrees, and distributed leader election.",

author = "Philippe Flajolet and Robert Sedgewick",

note = "Funding Information: *This work was partly supported by the ESPRIT Basic Research National Science Foundation grant no. CCR-9204846. *Corresponding author.",

year = "1995",

month = jun,

day = "26",

doi = "10.1016/0304-3975(94)00281-M",

language = "English (US)",

volume = "144",

pages = "101--124",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Mellin transforms and asymptotics

T2 - Finite differences and Rice's integrals

AU - Flajolet, Philippe

AU - Sedgewick, Robert

N1 - Funding Information: *This work was partly supported by the ESPRIT Basic Research National Science Foundation grant no. CCR-9204846. *Corresponding author.

PY - 1995/6/26

Y1 - 1995/6/26

N2 - High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin transform asymptotics, is put in perspective and illustrated by means of several examples related to combinatorics and the analysis of algorithms like digital tries, digital search trees, quadtrees, and distributed leader election.

AB - High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin transform asymptotics, is put in perspective and illustrated by means of several examples related to combinatorics and the analysis of algorithms like digital tries, digital search trees, quadtrees, and distributed leader election.

UR - https://www.scopus.com/pages/publications/0029325565

UR - https://www.scopus.com/pages/publications/0029325565#tab=citedBy

U2 - 10.1016/0304-3975(94)00281-M

DO - 10.1016/0304-3975(94)00281-M

M3 - Article

AN - SCOPUS:0029325565

SN - 0304-3975

VL - 144

SP - 101

EP - 124

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Mellin transforms and asymptotics: Finite differences and Rice's integrals

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this