Re: Quicksort

[Philippe Flajolet <Philippe.Flajolet@inria.fr>]

Thanks, Herb! It's very nice to know you're on-line!!

You're absolutely right. The reference you mention gives 
the estimate
                                   2        1
                              1 - ---- + O(----)
                                   n         2
                                            n
for the probability of NOT having a splitter (i.e., being
indecomposable). The authors use a recurrence based approach plus
a sort of limited bootstrapping. In fact, the argument I outlined 
could be used to show that there is a full asymptotic expansion
in descending powers of "n". My guess is that computing this expansion
to arbitrary order should be only a few lines of Maple code,
but I haven't tried it. Maybe the coefficients in that expansion
have some sort of a meaning, themselves. Who knows?

This points to a nice exercise in asymptotics, combinatorics,
and computer algebra.

Cheers,  Philippe
-- 
---------------------------------------------------
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
---------------------------------------------------