A330895 Numerator of the variance of the random number of comparisons in quicksort applied to lists of length n.

0, 0, 0, 2, 29, 46, 3049, 60574, 160599, 182789, 4913659, 1072364, 975570703, 1039388677, 5491155875, 92211937094, 6954047816459, 7225392149719, 2699717387790739, 2785123121790325, 573031978700759, 84009502802237, 45510401082365873, 46518885869845328

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

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) = numerator(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.

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.

Prog

(PARI) lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = numerator(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. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330875, A330876, A330907 (denominators).

Sequence in context: A340633 A252892 A256472 * A105893 A366692 A059799

Adjacent sequences: A330892 A330893 A330894 * A330896 A330897 A330898

Keyword

nonn,frac

Author

Petros Hadjicostas, May 01 2020

Status

approved