This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A360495 #52 Apr 26 2025 01:44:48
%S A360495 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 A360495 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 A360495 15,17,18,18,18,17,15,13,10,11,14,17,18,19,20,20,19,18,17,14,11
%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.
%C A360495 Also known in the literature as the selection problem, where T(n,k) is usually denoted by V_t(n), with t = k.
%C A360495 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 A360495 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 A360495 Terms are taken from Gasarch, Kelly and Pugh (1996), p. 92, Table 1, and from Oksanen (2005).
%D A360495 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 A360495 Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edition, Addison-Wesley, Reading, MA, 1998, pp. 207-216.
%D A360495 J. Schreier, On tournament elimination systems, Mathesis Polska 7, 1932, pp. 154-160 (in Polish).
%D A360495 Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp. 54-55.
%H A360495 Paolo Xausa, <a href="/A360495/b360495.txt">Table of n, a(n) for n = 1..91</a> (rows 1..13 of triangle, flattened).
%H A360495 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 A360495 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 A360495 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 A360495 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 A360495 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 A360495 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 A360495 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 A360495 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 A360495 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 A360495 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 A360495 Kenneth Oksanen, <a href="http://www.cs.hut.fi/~cessu/selection/">Selecting the i-th largest of n elements</a>, last updated 2005 (<a href="/A360495/a360495.pdf">local PDF version</a>, with permission).
%H A360495 Wikipedia, <a href="https://en.wikipedia.org/wiki/Selection_algorithm">Selection algorithm</a>.
%H A360495 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 A360495 T(n,1) = T(n,n) = n-1.
%F A360495 T(n,2) = n-2+ceiling(log_2(n)) = A080804(n-1), for n >= 2.
%F A360495 T(n,k) = T(n,n-k+1).
%F A360495 T(n,ceiling(n/2)) = A215476(n).
%F A360495 Some upper bounds:
%F A360495 T(n,k) <= n-k+(k-1)*ceiling(log_2(n-k+2)).
%F A360495 T(n,3) <= n+1+ceiling(log_2((n-1)/4))+ceiling(log_2((n-1)/5)).
%F A360495 T(n,k) <= 15*n-163, for n > 32.
%F A360495 Some lower bounds:
%F A360495 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 A360495 T(n,k) >= n+m-2*ceiling(sqrt(m)), where m = 2+ceiling(log_2(binomial(n,k)/(n-k+1))).
%e A360495 Triangle begins:
%e A360495 n\k| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
%e A360495 ---+-------------------------------------------------
%e A360495 1 | 0
%e A360495 2 | 1 1
%e A360495 3 | 2 3 2
%e A360495 4 | 3 4 4 3
%e A360495 5 | 4 6 6 6 4
%e A360495 6 | 5 7 8 8 7 5
%e A360495 7 | 6 8 10 10 10 8 6
%e A360495 8 | 7 9 11 12 12 11 9 7
%e A360495 9 | 8 11 12 14 14 14 12 11 8
%e A360495 10 | 9 12 14 15 16 16 15 14 12 9
%e A360495 11 | 10 13 15 17 18 18 18 17 15 13 10
%e A360495 12 | 11 14 17 18 19 20 20 19 18 17 14 11
%e A360495 13 | 12 15 18 20 21 22 23 22 21 20 18 15 12
%e A360495 14 | 13 16 19 21 23 24 ? ? 24 23 21 19 16 13
%e A360495 15 | 14 17 20 23 25 ? ? ? ? ? 25 23 20 17 14
%e A360495 ...
%Y A360495 Cf. A036604, A080804 (2nd column), A215476, A374236 (row sums).
%K A360495 nonn,nice,tabl,hard
%O A360495 1,4
%A A360495 _Paolo Xausa_, Feb 09 2023