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

DOI10.1137/0218054MaRDI QIDQ4729334zbMATH OpenOpenAlexFDO

Authors 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

analysis of algorithmsasymptotic analysisdigital trees and other data structuresfunctional equationinterval searching algorithmMellin transform

Mathematics Subject Classification ID

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

Recommendations

• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• On a recurrence equation arising in the analysis of conflict resolution algorithms
• An analysis of a contention resolution algorithm. Another approach
• Delay analysis of interval-searching contention resolution algorithms
• Limiting distribution of the collision resolution interval

Cited in

(8)

• Analytical depoissonization and its applications
• On the distribution for the duration of a randomized leader election algorithm
• On a recurrence equation arising in the analysis of conflict resolution algorithms
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• 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
• Mellin transforms and asymptotics: Harmonic sums

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729334)