Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 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.


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
  • Méthodes Aléatoires et Déterministes pour les processus de COllision, coalescence, de Fragmentation; Funder: French National Research Agency (ANR); Code: ANR-08-BLAN-0220

4 Documents citing this article

Consultation statistics

This page has been seen 249 times.
This article's PDF has been downloaded 343 times.