A036604 -id:A036604 - cp's OEIS frontend

A003070 a(n) = ceiling(log_2 n!).

0, 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 29, 33, 37, 41, 45, 49, 53, 57, 62, 66, 70, 75, 80, 84, 89, 94, 98, 103, 108, 113, 118, 123, 128, 133, 139, 144, 149, 154, 160, 165, 170, 176, 181, 187, 192, 198, 203, 209, 215, 220, 226, 232, 238, 243, 249, 255, 261, 267

Offset: 0

N. J. A. Sloane

nonn

a(n) is a lower bound for the minimum number of comparisons needed to sort n elements using a comparison sort (A036604). - Alex Costea, Mar 23 2019

D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Index entries for sequences related to sorting

Cf. A036604. Essentially the same as A072831.

[Ceiling(Log(2,Factorial(n))) : n in [0..70]]; // G. C. Greubel, Nov 03 2022

Array[Ceiling@ Log2[#!] &, 60, 0] (* Michael De Vlieger, Mar 27 2019 *)

[ceil(log(factorial(n),2)) for n in range(71)] # G. C. Greubel, Nov 03 2022

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264

Offset: 0

Daniel Krenn, Jun 20 2017

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.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.

a(9)-a(11) from Melanie Siebenhofer, Jan 29 2018

a(12)-a(13) from Melanie Siebenhofer, Feb 02 2018

A003075 Minimal number of comparisons needed for n-element sorting network.

Original entry on oeis.org

0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39

Offset: 1

N. J. A. Sloane

It is conjectured that the sequence continues (after 39) 45, 51, 56, 60, ...
a(13) <= 45 is mentioned in Knuth, Sorting and Searching, Vol. 2. a(9) was determined in 1991. - Ed Pegg Jr, Dec 05 2001.
Correction: the value for a(9) was not determined in the 1991 reference, which instead is about optimal depth. - Michael Codish, Jun 01 2014

R. W. Floyd and D. E. Knuth, The Bose-Nelson sorting problem, pp. 163-172 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.
H. Jullie, Lecture Notes in Comp. Sci. 929 (1995), 246-260.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (11).
I. Parberry, "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks", Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. Bundala, M. Codish, L. Cruz-Filipe et al., Optimal-Depth Sorting Networks, arXiv preprint arXiv:1412.5302 [cs.DS], 2014.
Michael Codish, Luís Cruz-Filipe, Michael Frank and Peter Schneider-Kamp, Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten), arXiv:1405.5754 [cs.DM], 2014.
Bert Dobbelaere, Smallest and fastest sorting networks for a given number of inputs
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is A000788).
Jannis Harder, Lower Size Bounds for Sorting Networks
Mariana Nagy, Vlad-Florin Drăgoi and Valeriu Beiu, Employing Sorting Nets for Designing Reliable Computing Nets, IEEE 20th International Conference on Nanotechnology (IEEE-NANO 2020) 370-375.
Ian Parberry, A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks
Ed Pegg Jr., Illustration of initial terms
Index entries for sequences related to sorting

A006282 is an upper bound. Cf. A036604, A067782 (minimal depth).

Updates from Ed Pegg Jr, Dec 05 2001
Correction and update: terms are exact for n<=10. The precise values for n=9 and n=10 are established in the reference from 2014 by Codish et al. - Michael Codish, Jun 01 2014
Entry revised by N. J. A. Sloane, Jun 02 2014
a(11)-a(12) from Jannis Harder, Dec 10 2019

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

Original entry on oeis.org

0, 2, 16, 112, 832, 6896, 62368, 619904, 6733312, 79268096, 1010644736, 13833177088, 203128772608, 3175336112128, 52723300200448, 927263962759168, 17221421451378688, 336720980854571008, 6911300635636400128, 148661140496700932096

Offset: 1

N. J. A. Sloane, Oct 06 2006

nonn

Sorting methods have been constructed such that the lower bound of f(n) is achieved for n=1, 2, 3, 4, 5, 6, 9 and 10. Y. Césari was the first to show that f(7) is not obtainable. He also constructed optimal solutions for n=9 and 10. L. Kollár showed that the minimum number of comparisons needed for n=7 is 62416. - Dmitry Kamenetsky, Jun 11 2015

Y. Césari, Questionnaire codage et tris, PhD Thesis, University of Paris, 1968.
D. E. Knuth, TAOCP, Vol. 3, Section 5.3.1.

Alois P. Heinz, Table of n, a(n) for n = 1..450
L. Kollár, Optimal sorting of seven element sets, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, 449-457.
Index entries for sequences related to sorting

Cf. A003070, A036604, A117628.

q:= n-> ceil(log[2](n!)):
a:= n-> (q(n)+1)*n! - 2^q(n):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 11 2015

q[n_] := Log[2, n!] // Ceiling; a[n_] := (q[n]+1)*n! - 2^q[n]; Array[a, 20] (* Jean-François Alcover, Feb 13 2016 *)

a(n) = { my(N=n!, q = ceil(log(N)/log(2))); return ((q+1)*N - 2^q);} \\ Michel Marcus, Apr 21 2013

Knuth gives an explicit formula.

a(n) = (q(n)+1)*n! - 2^q(n) with q(n) = A003070(n).

A360495 Triangle read by rows: T(n,k) is the minimum number of pairwise comparisons needed (in the worst case) to determine the k-th largest of n distinct numbers, for 1 <= k <= n.

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 4, 4, 3, 4, 6, 6, 6, 4, 5, 7, 8, 8, 7, 5, 6, 8, 10, 10, 10, 8, 6, 7, 9, 11, 12, 12, 11, 9, 7, 8, 11, 12, 14, 14, 14, 12, 11, 8, 9, 12, 14, 15, 16, 16, 15, 14, 12, 9, 10, 13, 15, 17, 18, 18, 18, 17, 15, 13, 10, 11, 14, 17, 18, 19, 20, 20, 19, 18, 17, 14, 11

Offset: 1

Paolo Xausa, Feb 09 2023

Also known in the literature as the selection problem, where T(n,k) is usually denoted by V_t(n), with t = k.
Knuth (1998) provides a historical background (the problem arose in 1883, when C. L. Dodgson--alias Lewis Carroll--proposed a better way to design tennis tournaments so that the true second- and third-best players could be determined) and a survey of recent results, including some upper and lower bounds (see Formula section).
No general formula for the exact value of T(n,k) is known, except for specific cases (e.g., k = 1 and k = 2).
Terms are taken from Gasarch, Kelly and Pugh (1996), p. 92, Table 1, and from Oksanen (2005).

			Triangle begins:
  n\k|  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  ---+-------------------------------------------------
   1 |  0
   2 |  1  1
   3 |  2  3  2
   4 |  3  4  4  3
   5 |  4  6  6  6  4
   6 |  5  7  8  8  7  5
   7 |  6  8 10 10 10  8  6
   8 |  7  9 11 12 12 11  9  7
   9 |  8 11 12 14 14 14 12 11  8
  10 |  9 12 14 15 16 16 15 14 12  9
  11 | 10 13 15 17 18 18 18 17 15 13 10
  12 | 11 14 17 18 19 20 20 19 18 17 14 11
  13 | 12 15 18 20 21 22 23 22 21 20 18 15 12
  14 | 13 16 19 21 23 24  ?  ? 24 23 21 19 16 13
  15 | 14 17 20 23 25  ?  ?  ?  ?  ? 25 23 20 17 14
  ...

Charles L. Dodgson, Lawn Tennis Tournaments: True Method of Assigning Prizes, with a Proof of the Fallacy of the Present Method, Macmillan, London, 1883.
Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edition, Addison-Wesley, Reading, MA, 1998, pp. 207-216.
J. Schreier, On tournament elimination systems, Mathesis Polska 7, 1932, pp. 154-160 (in Polish).
Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp. 54-55.

Paolo Xausa, Table of n, a(n) for n = 1..91 (rows 1..13 of triangle, flattened).
Martin Aigner, Selecting the top three elements, Discrete Applied Mathematics, Volume 4, Issue 4, August 1982, pp. 247-267.
Samuel W. Bent and John W. John, Finding the median requires 2n comparisons, STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, December 1985, pp. 213-216.
Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest and Robert E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, Volume 7, Issue 4, 1973, pp. 448-461.
Walter Cunto and J. Ian Munro, Average case selection, STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing, December 1984, pp. 369-375.
Jutta Eusterbrock, Errata to "Selecting the top three elements" by M. Aigner: A result of a computer-assisted proof search, Discrete Applied Mathematics, Volume 41, Issue 2, 26 January 1993, pp. 131-137.
William Gasarch, Wayne Kelly and William Pugh, Finding the i-th largest of n for small i,n, ACM SIGACT News, Volume 27, Issue 2, June 1996, pp. 88-96.
Abdollah Hadian and Milton Sobel, Selecting the t-th Largest Using Binary Errorless Comparisons, Technical Report 121, University of Minnesota, May 1969.
David G. Kirkpatrick, A Unified Lower Bound for Selection and Set Partitioning Problems, Journal of the ACM, Volume 28, Issue 1, January 1981, pp. 150-165.
David G. Kirkpatrick, Closing a Long-Standing Complexity Gap for Selection: V_3(42) = 50, in Brodnik, López-Ortiz, Raman and Viola (eds), Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066, Springer, Berlin, Heidelberg, 2013, pp. 61-76.
S. S. Kislitsyn, On the selection of the k-th element of an ordered set by pairwise comparisons, Sibirskii Matematicheskii Zhurnal, 1964, Volume 5, Number 3, pp. 557-564 (in Russian).
Kenneth Oksanen, Selecting the i-th largest of n elements, last updated 2005 (local PDF version, with permission).
Wikipedia, Selection algorithm.
Chee K. Yap, New upper bounds for selection, Communications of the ACM, Volume 19, Issue 9, September 1976, pp. 501-508.

Cf. A036604, A080804 (2nd column), A215476, A374236 (row sums).

T(n,1) = T(n,n) = n-1.
T(n,2) = n-2+ceiling(log_2(n)) = A080804(n-1), for n >= 2.
T(n,k) = T(n,n-k+1).
T(n,ceiling(n/2)) = A215476(n).
Some upper bounds:
T(n,k) <= n-k+(k-1)*ceiling(log_2(n-k+2)).
T(n,3) <= n+1+ceiling(log_2((n-1)/4))+ceiling(log_2((n-1)/5)).
T(n,k) <= 15*n-163, for n > 32.
Some lower bounds:
T(n,k) >= n+k-3+Sum_{j=0,k-2} ceiling(log_2((n-k+2)/(k+j))), for 2 <= k <= (n+1)/2.
T(n,k) >= n+m-2*ceiling(sqrt(m)), where m = 2+ceiling(log_2(binomial(n,k)/(n-k+1))).

cp's OEIS Frontend

A003070 a(n) = ceiling(log_2 n!).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A003075 Minimal number of comparisons needed for n-element sorting network.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A360495 Triangle read by rows: T(n,k) is the minimum number of pairwise comparisons needed (in the worst case) to determine the k-th largest of n distinct numbers, for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula