A repertoire for additive functionals of uniformly distributed m-ary search trees
| dc.creator | Fill, James Allen | |
| dc.creator | Kapur, Nevin | |
| dc.date | 2005-02-20 | |
| dc.date | 2005-04-25 | |
| dc.date.accessioned | 2026-07-07T05:17:19Z | |
| dc.date.available | 2026-07-07T05:17:19Z | |
| dc.description | 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 $α\geq 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) $\mathbf{1}_{n=m-1}$, which corresponds to the number of leaves. | |
| dc.description | 26 pages; v2 expands on the introduction by comparing the results with other probability models | |
| dc.identifier | https://arxiv.org/abs/math/0502422 | |
| dc.identifier | http://arxiv.org/abs/math/0502422 | |
| dc.identifier | Discrete Mathematics and Theoretical Computer Science Proceedings AD (2005) 105-114 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74261 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 68W40 (Primary) 60F05, 60C05 (Secondary) | |
| dc.title | A repertoire for additive functionals of uniformly distributed m-ary search trees | |
| dc.type | text |