A repertoire for additive functionals of uniformly distributed m-ary search trees

Details A repertoire for additive functionals of uniformly distributed m-ary search trees A repertoire for additive functionals of uniformly distributed m-ary search trees

2005-02-20

arxiv.org/abs/math/0502422v2

Discrete Mathematics and Theoretical Computer Science Proceedings AD (2005) 105-114

Mathematics

Probability

26 pages; v2 expands on the introduction by comparing the results with other probability models

Scientific paper

Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on $m$-ary search trees on $n$ keys with toll sequence (i) $n^\alpha$ with $\alpha \geq 0$ ($\alpha=0$ and $\alpha=1$ correspond roughly to the space requirement and total path length, respectively); (ii) $\ln \binom{n}{m-1}$, which corresponds to the so-called shape functional; and (iii) $\mathbf{1}_{n=m-1}$, which corresponds to the number of leaves.

Affiliated with

Also associated with

No associations

Rating

A repertoire for additive functionals of uniformly distributed 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 A repertoire for additive functionals of uniformly distributed m-ary search trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A repertoire for additive functionals of uniformly distributed m-ary search trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-24251