Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms

DOI10.1137/0608021zbMath0648.68059OpenAlexW2026159160MaRDI QIDQ3793730

Wojciech Szpankowski

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1471&context=cstech

zbMATH Keywords

asymptotic approximationrecurrence relationanalysis of algorithmsdata structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recurrences (11B37)

Related Items

On the distribution for the duration of a randomized leader election algorithm, The evaluation of an alternative sum with applications to the analysis of some data structures, Spectral resolution of a certain summation of series, Searching for losers, How to select a loser, How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An analysis of a contention resolution algorithm. Another approach
• Random multiple packet access: part-and-try algorithm
• Tree algorithms for packet broadcast channels
• Poisson multiple-access contention with binary feedback
• The complexity of generating an exponentially distributed variate
• Analytic Inequalities