ANALYSIS of ALGORITHMS, Bulletin Board

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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):
 
   asympt(add(coeff(series(1-1/add(k!*w^k,k=0..o)^2,w,o)\
   ,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