The Library
Almost sure asymptotics for the random binary search tree
Tools
Roberts, Matthew Iain (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), Vienna, Austria , 28 Jun- 2 Jul 2010. Published in: Proceedings of A of A '10 pp. 565-576. ISSN 1462-7264.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://www.dmtcs.org/dmtcs-ojs/index.php/proceedin...
Abstract
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 ! 1, 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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||
Journal or Publication Title: | Proceedings of A of A '10 | ||||
Publisher: | Discrete Mathematics & Theoretical Computer Science (DMTCS) | ||||
ISSN: | 1462-7264 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Page Range: | pp. 565-576 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Description: | DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) |
||||
Conference Paper Type: | Paper | ||||
Title of Event: | 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) | ||||
Type of Event: | Conference | ||||
Location of Event: | Vienna, Austria | ||||
Date(s) of Event: | 28 Jun- 2 Jul 2010 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |