james Allen fill ; Nevin Kapur - A repertoire for additive functionals of uniformly distributed m-ary search trees

dmtcs:3370 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3370
A repertoire for additive functionals of uniformly distributed m-ary search treesArticle

Authors: james Allen fill ; Nevin Kapur 1

  • 1 Department of Computer Science

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^α$ with $α ≥ 0 (α =0$ and $α =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) $$1$$_{n=m-1}$, which corresponds to the number of leaves.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: method of moments,limit laws,Hadamard products,additive functionals,search trees,leaves,space requirement,singularity analysis,shape functional,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]
Funding:
    Source : OpenAIRE Graph
  • Probability and Algorithms; Funder: National Science Foundation; Code: 0406104
  • CAREER: Computation Methods; Funder: National Science Foundation; Code: 0049092
  • Studies in Perfect Simulation and Combinatorial Probability; Funder: National Science Foundation; Code: 0104167

1 Document citing this article

Consultation statistics

This page has been seen 159 times.
This article's PDF has been downloaded 143 times.