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.

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

Author

Paolo Xausa, Feb 09 2023

Keywords

• nonn
• nice
• tabl
• hard

Comments

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).

Examples

			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
  ...
		

References

• 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.

Links

• 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.

Crossrefs

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

Formula

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))).