2003/06/30 by James Allen Fill, Nevin Kapur
Mathematics · #math.PR #msc:68W40 #msc:60F05 #msc:68P10 #msc:60E05
paper · pdf · doi:10.1002/rsa.20039
published as Random Structures Algorithms 26 (2005) 359-391 · 35 pages, 1 figure. Version 2 consists of expansion and rearragement of the introductory material to aid exposition and the shortening of Appendices A and B.2
arxiv created 2004/01/13 · arxiv updated 2009/11/30
We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of a simple additive form. Many important functionals including the space requirement, internal path length, and the so-called shape functional fall under this framework. The approach is based on establishing transfer theorems that link the order of growth of the input into a particular (deterministic) recurrence to the order of growth of the output. The transfer theorems are used in conjunction with the method of moments to establish limit laws. It is shown that (i) for small toll sequences (tn) [roughly, tn =O(n1 / 2)] we have asymptotic normality if m ≤ 26 and typically periodic behavior if m ≥ 27; (ii) for moderate toll sequences [roughly, tn = ω(n1 / 2) but tn = o(n)] we have convergence to non-normal distributions if m ≤ m0 (where m0 ≥ 26) and typically periodic behavior if m ≥ m0 + 1; and (iii) for large toll sequences [roughly, tn = ω(n)] we have convergence to non-normal distributions for all values of m.