A334935 The product of (n!)^2/8 and the variance of the random number of comparisons needed to sort a list of n distinct items using quicksort.

0, 0, 0, 1, 58, 3312, 219528, 17445312, 1665090432, 189515635200, 25472408256000, 4002577182720000, 728259627506688000, 152076300005855232000, 36154290403284480000000, 9714114050265240698880000, 2930311008702414783774720000, 986466808456816565267988480000, 368586443487759607372452986880000

Offset

0,5

Links

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

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) = ((n!)^2/8)*A330895(n)/A330907(n).

a(n) = ((n!)^2/8)*(n*(7*n + 13) - 2*(n + 1)*Sum_{k=1..n} 1/k - 4*(n + 1)^2*Sum_{k=1..n} 1/k^2).

Prog

(PARI) lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = ((n!)^2/8)*(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(0, va); }

Crossrefs

Cf. A330895, A330907.

Sequence in context: A225352 A278097 A299467 * A207278 A207474 A207530

Adjacent sequences: A334932 A334933 A334934 * A334936 A334937 A334938

Keyword

nonn

Author

Petros Hadjicostas, May 16 2020

Status

approved