DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

Almost sure asymptotics for the random binary search tree

Matthew I. Roberts

Abstract


We consider a (random permutation model) binary search tree with n nodes and give asymptotics on the loglog scale for the height Hn and saturation level hn of the tree as n→∞, both almost surely and in probability. We then consider the number Fn of particles at level Hn at time n, and show that Fn is unbounded almost surely.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional