Processing math: 22%

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 treesConference paper

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: leaves,space requirement,singularity analysis,shape functional,search trees,additive functionals,Hadamard products,limit laws,method of moments,[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 252 times.
This article's PDF has been downloaded 214 times.