Limiting Distribution for the Depth in PATRICIA Tries

DOI10.1137/0406016zbMath0798.68067OpenAlexW2033639590MaRDI QIDQ4695383

Bonita Rais, Wojciech Szpankowski, Philippe Jacquet

Publication date: 21 July 1993

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

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

zbMATH Keywords

Mellin transformanalysis of algorithmscomplex analysiscompact trieslimiting distribution for depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, On the distribution for the duration of a randomized leader election algorithm, Rounding of continuous random variables and oscillatory asymptotics, A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence, Asymptotic analysis of the moments of the Cantor distribution, Analytical depoissonization and its applications, Local limit theorems for finite and infinite urn models, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, Size and path length of Patricia tries: Dynamical sources context, Analysis of random LC tries, How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems, Renewal theory in the analysis of tries and strings, A binomial splitting process in connection with corner parking problems