Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees

Details Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees

2003-06-02

arxiv.org/abs/math/0306050v2

Random Structures Algorithms 26 (2005) 359-391

Mathematics

Probability

35 pages, 1 figure. Version 2 consists of expansion and rearragement of the introductory material to aid exposition and the sh

Scientific paper

10.1002/rsa.20039

We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of a simple additive form. Many important functionals including the space requirement, internal path length, and the so-called shape functional fall under this framework. The approach is based on establishing transfer theorems that link the order of growth of the input into a particular (deterministic) recurrence to the order of growth of the output. The transfer theorems are used in conjunction with the method of moments to establish limit laws. It is shown that (i) for small toll sequences $(t_n)$ [roughly, $t_n =O(n^{1 / 2})$] we have asymptotic normality if $m \leq 26$ and typically periodic behavior if $m \geq 27$; (ii) for moderate toll sequences [roughly, $t_n = \omega(n^{1 / 2})$ but $t_n = o(n)$] we have convergence to non-normal distributions if $m \leq m_0$ (where $m_0 \geq 26$) and typically periodic behavior if $m \geq m_0 + 1$; and (iii) for large toll sequences [roughly, $t_n = \omega(n)$] we have convergence to non-normal distributions for all values of m.

Affiliated with

Also associated with

No associations

Rating

Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78954