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

Author

Petros Hadjicostas, May 16 2020

Keywords

• nonn

Links

• 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.

Crossrefs

Cf. A330895, A330907.

Programs

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); }

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).