A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

0, 0, 2, 16, 116, 888, 7416, 67968, 682272, 7467840, 88678080, 1136712960, 15655438080, 230672171520, 3621985113600, 60392753971200, 1065907048550400, 19855856150323200, 389354639411404800, 8017578241634304000, 172991656889856000000, 3903132531903897600000

Offset

0,3

Comments

From Petros Hadjicostas, May 04 2020: (Start)

Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. (To get the number of key comparisons to sort all n! permutations of n elements by quicksort, multiply this number by n!.)

For this sequence, we have C = 4. The corresponding number of key comparisons to sort all n! permutations of n elements by quicksort when C = 3 is A063090(n). Thus, a(n) = A063090(n) - n!*n.

For more details, see my comments and references for sequences A093418, A096620, and A115107. (End)

Links

Daniel Krenn, Table of n, a(n) for n = 0..100

Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Lucky Cars and the Quicksort Algorithm, arXiv:2306.13065 [math.CO], 2023.

Index entries for sequences related to sorting

Formula

a(n) = n!*(2*(n+1)*H(n) - 4*n).

c(n) = a(n) / n! satisfies c(n) = (n-1) + 2/n * Sum_{i < n} c(i).

a(n) = 2*A002538(n-1), n >= 2. - Omar E. Pol, Jun 20 2017

E.g.f.: -2*log(1-x)/(1-x)^2 - 2*x/(1-x)^2. - Daniel Krenn, Jun 20 2017

a(n) = ((2*n^2-3*n-1)*a(n-1) -(n-1)^2*n*a(n-2))/(n-2) for n >= 3, a(n) = n*(n-1) for n < 3. - Alois P. Heinz, Jun 21 2017

From Petros Hadjicostas, May 03 2020: (Start)

a(n) = A063090(n) - n!*n for n >= 1.

a(n) = n!*A115107(n)/A096620(n) = n!*(-n + A093418(n)/A096620(n)). (End)

Maple

a:= proc(n) option remember; `if`(n<3, n*(n-1),
      ((2*n^2-3*n-1)*a(n-1)-(n-1)^2*n*a(n-2))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 21 2017

Mathematica

a[n_] := n! (2(n+1)HarmonicNumber[n] - 4n);
a /@ Range[0, 25] (* Jean-François Alcover, Oct 29 2020 *)

Prog

(SageMath) [n.factorial() * (2*(n+1)*sum(1/k for k in srange(1, n+1)) - 4*n) for n in srange(21)]
(SageMath) # alternative using the recurrence relation
@cached_function
def c(n):
    if n <= 1:
        return 0
    return (n - 1) + 2/n*sum(c(i) for i in srange(n))
[n.factorial() * c(n) for n in srange(21)]

Crossrefs

Cf. A063090, A093418, A096620, A115107, A117627, A117628, A159324, A288965.

Sequence in context: A208364 A207711 A162723 * A193289 A159324 A088755

Adjacent sequences: A288961 A288962 A288963 * A288965 A288966 A288967

Keyword

nonn

Author

Daniel Krenn, Jun 20 2017

Status

approved