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
Examples
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.
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
- 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
Programs
-
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);}
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.