|
| |
|
|
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.
|
|
5
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
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, Wayne and Pugh (1996), p. 92, Table 1, and from Oksanen (2005).
|
|
|
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
|
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.
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.
|
|
|
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).
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))).
|
|
|
EXAMPLE
|
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
...
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
