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

%I #43 Jul 05 2024 02:25:30

%S 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,

%T 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,

%U 15,17,18,18,18,17,15,13,10,11,14,17,18,19,20,20,19,18,17,14,11

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

%C Also known in the literature as the selection problem, where T(n,k) is usually denoted by V_t(n), with t = k.

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

%C No general formula for the exact value of T(n,k) is known, except for specific cases (e.g., k = 1 and k = 2).

%C Terms are taken from Gasarch, Wayne and Pugh (1996), p. 92, Table 1, and from Oksanen (2005).

%D Charles L. Dodgson, Lawn Tennis Tournaments: True Method of Assigning Prizes, with a Proof of the Fallacy of the Present Method, Macmillan, London, 1883.

%D Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edition, Addison-Wesley, Reading, MA, 1998, pp. 207-216.

%D J. Schreier, On tournament elimination systems, Mathesis Polska 7, 1932, pp. 154-160 (in Polish).

%D Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp. 54-55.

%H Paolo Xausa, <a href="/A360495/b360495.txt">Table of n, a(n) for n = 1..91</a> (rows 1..13 of triangle, flattened).

%H Martin Aigner, <a href="https://doi.org/10.1016/0166-218X(82)90048-8">Selecting the top three elements</a>, Discrete Applied Mathematics, Volume 4, Issue 4, August 1982, pp. 247-267.

%H Samuel W. Bent and John W. John, <a href="https://doi.org/10.1145/22145.22169">Finding the median requires 2n comparisons</a>, STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, December 1985, pp. 213-216.

%H Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest and Robert E. Tarjan, <a href="https://doi.org/10.1016/S0022-0000(73)80033-9">Time bounds for selection</a>, Journal of Computer and System Sciences, Volume 7, Issue 4, 1973, pp. 448-461.

%H Walter Cunto and J. Ian Munro, <a href="https://doi.org/10.1145/800057.808702">Average case selection</a>, STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing, December 1984, pp. 369-375.

%H Jutta Eusterbrock, <a href="https://doi.org/10.1016/0166-218X(93)90033-K">Errata to "Selecting the top three elements" by M. Aigner: A result of a computer-assisted proof search</a>, Discrete Applied Mathematics, Volume 41, Issue 2, 26 January 1993, pp. 131-137.

%H William Gasarch, Wayne Kelly and William Pugh, <a href="https://doi.org/10.1145/235767.235772">Finding the i-th largest of n for small i,n</a>, ACM SIGACT News, Volume 27, Issue 2, June 1996, pp. 88-96.

%H Abdollah Hadian and Milton Sobel, <a href="https://hdl.handle.net/11299/199105">Selecting the t-th Largest Using Binary Errorless Comparisons</a>, Technical Report 121, University of Minnesota, May 1969.

%H David G. Kirkpatrick, <a href="https://doi.org/10.1145/322234.322245">A Unified Lower Bound for Selection and Set Partitioning Problems</a>, Journal of the ACM, Volume 28, Issue 1, January 1981, pp. 150-165.

%H David G. Kirkpatrick, <a href="https://doi.org/10.1007/978-3-642-40273-9_6">Closing a Long-Standing Complexity Gap for Selection: V_3(42) = 50</a>, 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.

%H S. S. Kislitsyn, <a href="https://www.mathnet.ru/eng/smj5024">On the selection of the k-th element of an ordered set by pairwise comparisons</a>, Sibirskii Matematicheskii Zhurnal, 1964, Volume 5, Number 3, pp. 557-564 (in Russian).

%H Kenneth Oksanen, <a href="http://www.cs.hut.fi/~cessu/selection/">Selecting the i-th largest of n elements</a>, last updated 2005.

%H Kenneth Oksanen, <a href="/A360495/a360495.pdf">Selecting the i-th largest of n elements</a>, local PDF version.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Selection_algorithm">Selection algorithm</a>.

%H Chee K. Yap, <a href="https://doi.org/10.1145/360336.360339">New upper bounds for selection</a>, Communications of the ACM, Volume 19, Issue 9, September 1976, pp. 501-508.

%F T(n,1) = T(n,n) = n-1.

%F T(n,2) = n-2+ceiling(log_2(n)) = A080804(n-1), for n >= 2.

%F T(n,k) = T(n,n-k+1).

%F T(n,ceiling(n/2)) = A215476(n).

%F Some upper bounds:

%F T(n,k) <= n-k+(k-1)*ceiling(log_2(n-k+2)).

%F T(n,3) <= n+1+ceiling(log_2((n-1)/4))+ceiling(log_2((n-1)/5)).

%F T(n,k) <= 15*n-163, for n > 32.

%F Some lower bounds:

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

%F T(n,k) >= n+m-2*ceiling(sqrt(m)), where m = 2+ceiling(log_2(binomial(n,k)/(n-k+1))).

%e Triangle begins:

%e n\k| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

%e ---+-------------------------------------------------

%e 1 | 0

%e 2 | 1 1

%e 3 | 2 3 2

%e 4 | 3 4 4 3

%e 5 | 4 6 6 6 4

%e 6 | 5 7 8 8 7 5

%e 7 | 6 8 10 10 10 8 6

%e 8 | 7 9 11 12 12 11 9 7

%e 9 | 8 11 12 14 14 14 12 11 8

%e 10 | 9 12 14 15 16 16 15 14 12 9

%e 11 | 10 13 15 17 18 18 18 17 15 13 10

%e 12 | 11 14 17 18 19 20 20 19 18 17 14 11

%e 13 | 12 15 18 20 21 22 23 22 21 20 18 15 12

%e 14 | 13 16 19 21 23 24 ? ? 24 23 21 19 16 13

%e 15 | 14 17 20 23 25 ? ? ? ? ? 25 23 20 17 14

%e ...

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

%K nonn,nice,tabl,hard

%O 1,4

%A _Paolo Xausa_, Feb 09 2023