{
  "id": "math/0405144",
  "version": "v1",
  "published": "2004-05-08T04:20:38.000Z",
  "updated": "2004-05-08T04:20:38.000Z",
  "title": "The space requirement of m-ary search trees: distributional asymptotics for m >= 27",
  "authors": [
    "James Allen Fill",
    "Nevin Kapur"
  ],
  "comment": "10 pages, 1 figure",
  "categories": [
    "math.PR"
  ],
  "abstract": "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 $\\mu (n+1) + 2\\Re{[\\Lambda n^{\\lambda_2}]} + \\epsilon_n n^{\\Re{\\lambda_2}}$, where $\\mu$ and $\\lambda_2$ are certain constants, $\\Lambda$ is a complex-valued random variable, and $\\epsilon_n \\to 0$ a.s. and in $L^2$ as $n \\to \\infty$. Using the contraction method, we identify the distribution of $\\Lambda$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-05-08T04:20:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60F05"
    ],
    "keywords": [
      "m-ary search trees",
      "space requirement",
      "distributional asymptotics",
      "random permutation model",
      "contraction method"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......5144F"
    }
  }
}