The space requirement of m-ary search trees: distributional asymptotics for m >= 27
| dc.creator | Fill, James Allen | |
| dc.creator | Kapur, Nevin | |
| dc.date | 2004-05-08 | |
| dc.date.accessioned | 2026-07-07T05:08:02Z | |
| dc.date.available | 2026-07-07T05:08:02Z | |
| dc.description | We study the space requirement of $m$-ary search trees under the random permutation model when $m \geq 27$ is fixed. Chauvin and Pouyanne have shown recently that $X_n$, the space requirement of an $m$-ary search tree on $n$ keys, equals $μ(n+1) + 2\Re{[Λn^{λ_2}]} + ε_n n^{\Re{λ_2}}$, where $μ$ and $λ_2$ are certain constants, $Λ$ is a complex-valued random variable, and $ε_n \to 0$ a.s. and in $L^2$ as $n \to \infty$. Using the contraction method, we identify the distribution of $Λ$. | |
| dc.description | 10 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/math/0405144 | |
| dc.identifier | http://arxiv.org/abs/math/0405144 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71103 | |
| dc.subject | Probability | |
| dc.subject | 60C05; 60F05 | |
| dc.title | The space requirement of m-ary search trees: distributional asymptotics for m >= 27 | |
| dc.type | text |