A330907 Denominator of the variance of the random number of comparisons in quicksort applied to lists of length n.

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

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