Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation

DOI10.1137/0218054zbMath0679.68052OpenAlexW1990901261MaRDI QIDQ4729334

Wojciech Szpankowski, Philippe Jacquet

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8d0476b04bfcf8a023b3dafc723fa31355222009

zbMATH Keywords

Mellin transformfunctional equationanalysis of algorithmsasymptotic analysisdigital trees and other data structuresinterval searching algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Iteration theory, iterative and composite equations (39B12)

Related Items (6)

On the distribution for the duration of a randomized leader election algorithm ⋮ Analytical depoissonization and its applications ⋮ Mellin transforms and asymptotics: Harmonic sums ⋮ The Diagonal Poisson Transform and its application to the analysis of a hashing scheme ⋮ How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems ⋮ The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects

This page was built for publication: Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation