The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A330895 Numerator of the variance of the random number of comparisons in quicksort applied to lists of length n. 5
 0, 0, 0, 2, 29, 46, 3049, 60574, 160599, 182789, 4913659, 1072364, 975570703, 1039388677, 5491155875, 92211937094, 6954047816459, 7225392149719, 2699717387790739, 2785123121790325, 573031978700759, 84009502802237, 45510401082365873, 46518885869845328 (list; graph; refs; listen; history; text; internal format)
 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 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 A059799 A142969 Adjacent sequences:  A330892 A330893 A330894 * A330896 A330897 A330898 KEYWORD nonn,frac AUTHOR Petros Hadjicostas, May 01 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 25 23:39 EDT 2021. Contains 346294 sequences. (Running on oeis4.)