uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
A functional limit theorem for the profile of search trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2008 (English)In: The Annals of Applied Probability, ISSN 1050-5164, Vol. 18, no 1, 288-233 p.Article in journal (Refereed) Published
Abstract [en]

We study the profile X-n,X-k of random search trees including binary search trees and m-ary search trees. Our main result is a functional limit theorem of the normalized profile X-n,X-k/EXn,k for k = [alpha logn] in a certain range of alpha. A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.

Place, publisher, year, edition, pages
2008. Vol. 18, no 1, 288-233 p.
Keyword [en]
functional limit theorem, search trees, profile of trees, random trees, analysis of algorithms
National Category
URN: urn:nbn:se:uu:diva-106265DOI: 10.1214/07-AAP457ISI: 000252750300012OAI: oai:DiVA.org:uu-106265DiVA: diva2:224358
Available from: 2009-06-17 Created: 2009-06-17 Last updated: 2010-01-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of Mathematics
In the same journal
The Annals of Applied Probability

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 150 hits
ReferencesLink to record
Permanent link

Direct link