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

%I #25 May 09 2020 03:36:05

%S 1,1,1,9,36,25,900,11025,19600,15876,317520,53361,38419920,33127380,

%T 144288144,2029052025,129859329600,115831315600,37529346254400,

%U 33870234994596,6144260316480,799769421360,387088399938240,355503061748835,40953952713465792,37864231428870000,316002721554520000,2056839142975402500,1612561888092715560000

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

%D 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.

%H S. B. Ekhad and D. Zeilberger, <a href="https://arxiv.org/abs/1903.03708">A detailed analysis of quicksort running time</a>, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.

%H V. Iliopoulos, <a href="https://arxiv.org/abs/1503.02504">The quicksort algorithm and related topics</a>, arXiv:1503.02504 [cs.DS], 2015.

%H V. Iliopoulos and D. Penman, <a href="https://arxiv.org/abs/1006.4063">Variance of the number of comparisons of randomized quicksort</a>, arXiv:1006.4063 [math.PR], 2010.

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

%F 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

%e 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.

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

%p seq(a(n), n=0..28); # _Peter Luschny_, May 02 2020

%o (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); }

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

%K nonn,frac

%O 0,4

%A _Petros Hadjicostas_, May 01 2020