The evaluation of an alternative sum with applications to the analysis of some data structures

DOI10.1016/0020-0190(88)90137-8zbMath0657.68071OpenAlexW2079346522MaRDI QIDQ1111028

Wojciech Szpankowski

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90137-8

zbMATH Keywords

data structuresasymptotic enumerationdigital search trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, An asymptotic study of a recursion occurring in the analysis of an algorithm on broadcast communication, Explicit and asymptotic formulae for the expected values of the order statistics of the Cantor distribution, On the balance property of Patricia tries: External path length viewpoint, A characterization of digital search trees from the successful search viewpoint, Mellin transforms and asymptotics: Finite differences and Rice's integrals, A note on binomial recurrences arising in the analysis of algorithms, How to select a loser, On The variance of the extremal path length in a symmetric digital trie, Yet another application of a binomial recurrence. Order statistics, The number of winners in a discrete geometrically distributed sample

Cites Work

• On the performance evaluation of extendible hashing and trie searching
• On a recurrence equation arising in the analysis of conflict resolution algorithms
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Digital Search Trees Revisited
• Some results on V-ary asymmetric tries
• Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item