Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme

DOI10.1137/S0097539799356812zbMath0968.68067MaRDI QIDQ4507378

Wojciech Szpankowski, Charles Knessl

Publication date: 18 October 2000

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

zbMATH Keywords

Laplace transformlinearizationWKB methodmatched asymptoticssaddle point methoddigital search treeselliptic theta functionLempel-Ziv algorithmheight distributionlongest phrase distribution

Mathematics Subject Classification ID

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

Related Items (6)

Phase transition in a generalized Eden growth model on a tree ⋮ Some new results for McKean's graphs with applications to Kac's equation ⋮ Node profiles of symmetric digital search trees: Concentration properties ⋮ Continuous-time digital search tree and a border aggregation model ⋮ The expected profile of digital search trees ⋮ The height of a binary search tree: the limiting distribution perspective.

This page was built for publication: Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme