Matthew Roberts - Almost sure asymptotics for the random binary search tree

dmtcs:2775 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2775
Almost sure asymptotics for the random binary search treeConference paper

Authors: Matthew Roberts 1

  • 1 Laboratoire de Probabilités et Modèles Aléatoires

We consider a (random permutation model) binary search tree with $n$ nodes and give asymptotics on the $\log$ $\log$ 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.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Binary search tree,Random permutation model,Yule tree,Quicksort,Branching random walk,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • Funder: French National Research Agency (ANR); Code: ANR-08-BLAN-0220

4 Documents citing this article

Consultation statistics

This page has been seen 252 times.
This article's PDF has been downloaded 352 times.