cp's OEIS Frontend

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)

a(n) is the sum over all permutations, p, of {1, ..., n} of the number of comparisons required to find all the entries in the tree formed when the order of insertion is p(1), p(2), ... p(n). To derive the formula given, first group the trees according to the value of k = p(1). For a given k, p determines a permutation of {1, ..., k-1} that gives the structure of the left subtree. By symmetry, the contribution of the right subtrees will be the same as the left subtrees. Now count and simplify.

a(n) mod n is n-2 or 0 depending on whether n is prime or not. - Gary Detlefs, May 28 2012

The 3 pivot elements are chosen from fixed indices (e.g., the last 3 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

The 4 pivot elements are chosen from fixed indices (e.g. the last 4 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.

First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence

Sum_{r=0..p} Stirling1(p+2, r+1)*B(p-r)/(p-r)! + Sum_{r=0..p} F(r)*F(p-r) = 0, where F(r) = Sum_{i=0..r} Stirling1(r+1,i+1)*G(r-i) and G(k) = Sum_{a=0..k} (-1)^a*B(k-a)/(a!*(k-a)!*2^a).

Then A(n) = L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.

Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants (-2)^n*A(n), which they denote by a_n. See also Finch (2020).

The Maple program below is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.

The rest of the references give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).

Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.

First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence

Sum_{r=0..p} Stirling1(p+2, r+1)*B(p-r)/(p-r)! + Sum_{r=0..p} F(r)*F(p-r) = 0, where F(r) = Sum_{i=0..r} Stirling1(r+1,i+1)*G(r-i) and G(k) = Sum_{a=0..k} (-1)^a*B(k-a)/(a!*(k-a)!*2^a).

Then A(n) = L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.

Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants (-2)^n*A(n), which they denote by a_n. See also Finch (2020).

The Maple program given in A330852 is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.

For a list of references about the theory of the limiting distribution of the number of comparisons in quicksort, which we do not discuss here, see the ones for sequence A330852.

Let X_n be the number of comparisons needed to sort a list of n distinct numbers by quicksort. Then E(X_n) = A115107(n)/A096620(n) = -4*n + + 2*(1+n)*HarmonicNumber(n) or E(X_n) = A093418(n)/A096620(n) = -3*n + + 2*(1+n)*HarmonicNumber(n) depending on the assumptions.

Régnier (1989) and Rösler (1991) proved that (X_n - E(X_n))/n converges a.s. (and in other modes of convergence) to a non-degenerate r.v. X. Rösler proved the existence of all moments for X and Tan and Hadjicostas (1995) proved that it has a density w.r.t. to the Lebesgue measure. Fill and Janson (2000, 2002) proved many other properties of the distribution of X.

Hennequin (1989, 1991) calculated moments and cumulants of X. He proved that mu(n) = E(X^n) is a linear combination of a finite number of zeta values at positive integer arguments with rational coefficients plus a rational constant c(n). It is the numerators of this constant term c(n) of mu(n) that we tabulate here, while the denominators are in A330876.

Hennequin (1991) proved that the n-th cumulant of X for n >= 2 is k(n) = (-2)^n*(A(n) - (n-1)!*zeta(n)), where A(n) = A330852(n)/A330860(n) with A(0) = 1 and A(1) = 0. Also, (-2)^n*A(n) = A330875(n)/A330876(n); see Hoffman and Kuba (2019-2020) and Finch (2020).

Actually, Hoffman and Kuba (2019-2020, Proposition 17) express the constants c(n) in terms of "tiered binomial coefficients". Finch (2020) uses their results to write a Mathematica program with which he calculates at least c(2) - c(8). The values c(2) - c(8) have also been calculated indirectly by Ekhad and Zeilberger (2019).

Because moments and cumulants are connected via the relationship mu(n) = Sum_{s=0..n-1} binomial(n-1,s)*k(s+1)*mu(n-1-s) (e.g., see Tan and Hadjicostas (1993)), we easily deduce that c(n) = Sum_{s=0..n-1} binomial(n-1,s)*(-2)^(s+1)*A(s+1)*c(n-1-s) for n >= 1 because c(1) = A(1) = mu(1) = k(1) = 0 and k(n) = (-2)^n*A(n) - (-2)^n*(n-1)!*zeta(n) for n >= 2 and c(n) is the constant term of mu(n).

Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.

First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence

Sum_{r=0..p} Stirling1(p+2, r+1)*B(p-r)/(p-r)! + Sum_{r=0..p} F(r)*F(p-r) = 0, where F(r) = Sum_{i=0..r} Stirling1(r+1,i+1)*G(r-i) and G(k) = Sum_{a=0..k} (-1)^a*B(k-a)/(a!*(k-a)!*2^a).

Then fr(n) = (-2)^n*L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.

Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants fr(n), which they denote by a_n. See also Finch (2020).

Tan and Hadjicostas (1993) used a Maple program (an update of which can be found in A330852) to tabulate the numbers (fr(n)/(-2)^n: n >= 0).

Sequence A330852 contains additional references that give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).

Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.

First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence

Sum_{r=0..p} Stirling1(p+2, r+1)*B(p-r)/(p-r)! + Sum_{r=0..p} F(r)*F(p-r) = 0, where F(r) = Sum_{i=0..r} Stirling1(r+1,i+1)*G(r-i) and G(k) = Sum_{a=0..k} (-1)^a*B(k-a)/(a!*(k-a)!*2^a).

Then fr(n) = (-2)^n*L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.

Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants fr(n), which they denote by a_n. See also Finch (2020).

Tan and Hadjicostas (1993) used a Maple program (an update of which can be found in A330852) to tabulate the numbers (fr(n)/(-2)^n: n >= 0).

Sequence A330852 contains additional references that give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).