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)
CountryAustria
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

    Roberts, M. I. (2010). Almost sure asymptotics for the random binary search tree. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (pp. 565-576). (DMTCS Proceedings). DMTCS.