{
  "id": "1903.07775",
  "version": "v1",
  "published": "2019-03-19T00:04:32.000Z",
  "updated": "2019-03-19T00:04:32.000Z",
  "title": "QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations",
  "authors": [
    "James Allen Fill",
    "Wei-Chun Hung"
  ],
  "comment": "15 pages; submitted for publication in January, 2019",
  "categories": [
    "math.PR",
    "cs.DS"
  ],
  "abstract": "We substantially refine asymptotic logarithmic upper bounds produced by Svante Janson (2015) on the right tail of the limiting QuickSort distribution function $F$ and by Fill and Hung (2018) on the right tails of the corresponding density $f$ and of the absolute derivatives of $f$ of each order. For example, we establish an upper bound on $\\log[1 - F(x)]$ that matches conjectured asymptotics of Knessl and Szpankowski (1999) through terms of order $(\\log x)^2$; the corresponding order for the Janson (2015) bound is the lead order, $x \\log x$. Using the refined asymptotic bounds on $F$, we derive right-tail large deviation (LD) results for the distribution of the number of comparisons required by QuickSort that substantially sharpen the two-sided LD results of McDiarmid and Hayward (1996).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-19T00:04:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68P10",
      "60E05",
      "60C05"
    ],
    "keywords": [
      "large deviation",
      "right-tail asymptotics",
      "limiting distribution",
      "refine asymptotic logarithmic upper bounds",
      "substantially refine asymptotic logarithmic upper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}