ANALYSIS of ALGORITHMS, Bulletin Board

# Re: Quicksort

```I couldn't resist and wound up doing the exercise I had
suggested. Here's a one-liner (in Maple) to get an asymptotic
expansion to arbitrary order (the variable \$o\$) of the
proportion of decomposable perms (the ones that have a
splitter):

,w,k)/mul(n-j,j=0..k-1),k=0..o),n,o);

which, when executed with ``o:=12;'' yields

1      5      32    253   2381   25912   319339
2/n + ---- + ---- + ---- + --- + ---- + ----- + ------
2      3      4     5      6      7        8
n      n      n     n      n      n        n

4388949   66495386   1100521327      1
+ ------- + -------- + ---------- + O(---)
9         10          11          12
n         n           n           n

The accuracy of this expansion is already of 10 significant
digits when n=50.

Comment: Examine the dominant terms in the convolutions for
coefficients of I(z)=(P(z)-1)-(P(z)-1)^2+...
[see previous messages].
Asymptotically, the only terms that matter are the ones
nvolving one ``large'' factorial and a few small factorials.
For instance:
(P(z)-1)^2:     1!*(n-1), 2!*(n-2)!, etc
(P(z)-1)^3:     1!*1!*(n-2), 1!*2!*(n-3)!, etc
Closer examination of the process reveals that the asymptotic expansion
is obtained by considering
S(w) = 2*(P(w)-1)+3*(P(w)-1)^2+... = 1/P(w)^2-1.
and applying the transformation:
w^k ==> 1/(n*(n-1)*...*(n-k+1)).
The Maple programme precisely implements a truncated version.

We observe that the coefficients are all positive and indeed
they are expressed as convolutions of the number of irreducible
perms (because of 1/P(z)) and of Stirling partition numbers.
Naturally, a detailed proof, though routine, will require some
care.

--
---------------------------------------------------
Philippe Flajolet
Algorithms Project, INRIA Rocquencourt
F-78153 Le Chesnay (France)
Tel: +33 (1) 39.63.56.26 / 39.63.54.43 [secr.]
Fax: +33 (1) 39.63.55.96
E-mail: Philippe.Flajolet@inria.fr
WWW: http://www-rocq.inria.fr/algo/flajolet/index.html
+++ANALYSIS of ALGORITHMS pages:
http://www-rocq.inria.fr/algo/AofA/index.html
---------------------------------------------------
```

Date Prev | Date Next | Date Index | Thread Index