### Abstract

Original language | English |
---|---|

Title of host publication | 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) |

Publisher | DMTCS |

Pages | 565-576 |

Number of pages | 12 |

Publication status | Published - 2010 |

Event | 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - Vienna, Austria Duration: 27 Jun 2010 → 1 Jul 2010 |

### Publication series

Name | DMTCS Proceedings |
---|

### Conference

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

Country | Austria |

City | Vienna |

Period | 27/06/10 → 1/07/10 |

### Fingerprint

### Cite this

*21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)*(pp. 565-576). (DMTCS Proceedings). DMTCS.

**Almost sure asymptotics for the random binary search tree.** / Roberts, Matthew I.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10).*DMTCS Proceedings, DMTCS, pp. 565-576, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), Vienna, Austria, 27/06/10.

}

TY - GEN

T1 - Almost sure asymptotics for the random binary search tree

AU - Roberts, Matthew I

PY - 2010

Y1 - 2010

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

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

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0139

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0139/3334

M3 - Conference contribution

T3 - DMTCS Proceedings

SP - 565

EP - 576

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

PB - DMTCS

ER -