login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A330907 Denominator of the variance of the random number of comparisons in quicksort applied to lists of length n. 5
1, 1, 1, 9, 36, 25, 900, 11025, 19600, 15876, 317520, 53361, 38419920, 33127380, 144288144, 2029052025, 129859329600, 115831315600, 37529346254400, 33870234994596, 6144260316480, 799769421360, 387088399938240, 355503061748835, 40953952713465792, 37864231428870000, 316002721554520000, 2056839142975402500, 1612561888092715560000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

REFERENCES

D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973; see answer to Ex. 8(a) of Section 6.2.2.

LINKS

Table of n, a(n) for n=0..28.

S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.

V. Iliopoulos, The quicksort algorithm and related topics, arXiv:1503.02504 [cs.DS], 2015.

V. Iliopoulos and D. Penman, Variance of the number of comparisons of randomized quicksort, arXiv:1006.4063 [math.PR], 2010.

FORMULA

a(n) = denominator(fr(n)), where fr(n) = n*(7*n + 13) - 2*(n+1)*Sum_{k=1..n} (1/k) - 4*(n+1)^2*Sum_{k=1..n} (1/k^2).

a(n) = denominator(2*(n+1)*(H(n,1) + 2*(n+1)*H(n,2)), where H(n,s) are the generalized harmonic numbers. - Peter Luschny, May 02 2020

EXAMPLE

The variances are: 0, 0, 0, 2/9, 29/36, 46/25, 3049/900, 60574/11025, 160599/19600, 182789/15876, 4913659/317520, 1072364/53361, ... = A330895/A330907.

MAPLE

a := n -> denom(2*(n+1)*(harmonic(n, 1) + 2*(n+1)*harmonic(n, 2))):

seq(a(n), n=0..28); # Peter Luschny, May 02 2020

PROG

(PARI) lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = denominator(n*(7*n+13) - 2*(n+1)*sum(k=1, n, 1/k) - 4*(n+1)^2*sum(k=1, n, 1/k^2))); concat(1, va); }

CROSSREFS

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330875, A330876, A330895 (numerators).

Sequence in context: A271425 A267081 A020297 * A231666 A143224 A192610

Adjacent sequences:  A330904 A330905 A330906 * A330908 A330909 A330910

KEYWORD

nonn,frac

AUTHOR

Petros Hadjicostas, May 01 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 27 13:36 EDT 2021. Contains 346306 sequences. (Running on oeis4.)