Almost sure asymptotics for the random binary search tree

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a (random permutation model) binary search tree with n nodes and give asymptotics on the loglog scale for the height H_n and saturation level h_n of the tree as n\to\infty, both almost surely and in probability. We then consider the number F_n of particles at level H_n at time n, and show that F_n is unbounded almost surely.
Original languageEnglish
Title of host publication21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PublisherDMTCS
Pages565-576
Number of pages12
Publication statusPublished - 2010
Event21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - Vienna, Austria
Duration: 27 Jun 20101 Jul 2010

Publication series

NameDMTCS Proceedings

Conference

Conference21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Country/TerritoryAustria
CityVienna
Period27/06/101/07/10

Fingerprint

Dive into the research topics of 'Almost sure asymptotics for the random binary search tree'. Together they form a unique fingerprint.

Cite this