{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:08Z","timestamp":1787340608559,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1982,8]]},"abstract":"<jats:p>Let $\\bar V_k (n)$ be the minimum average number of pairwise comparisons needed to find the kth largest of n numbers $(k \\geqq 2)$, assuming that all $n!$ orderings are equally likely. D. W. Matula proved that, for some absolute constant c, $\\bar V_k (n) - n \\leqq ck\\ln \\ln n$ as $n \\to \\infty $. In the present paper, we show that there exists an absolute constant $c' &gt; 0$ such that $\\bar V_k (n) - n \\geqq c'k\\ln \\ln n$ as $n \\to \\infty $, proving a conjecture of Matula.<\/jats:p>","DOI":"10.1137\/0211034","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:24:24Z","timestamp":1109226264000},"page":"428-447","source":"Crossref","is-referenced-by-count":6,"title":["On the Average-Case Complexity of Selecting the\n                    <i>k<\/i>\n                    th Best"],"prefix":"10.1137","volume":"11","author":[{"given":"Andrew C.","family":"Yao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. Frances","family":"Yao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322128"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0601028"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0205010"},{"key":"R5","unstructured":"D. G. Kirkpatrick,  Topics in the complexity of combinatorial algorithms, Technical Report, TR 74, Computer Science Department, University of Toronto, Toronto, Canada,  1974"},{"key":"R6","first-page":"19","volume-title":"Information processing 71 (Proc. IFIP Congress, Ljubljana, 1971), Vol. 1: Foundations and systems","author":"Knuth Donald E.","year":"1972"},{"key":"R7","volume-title":"The art of computer programming, vol.1, Fundamental Algorithms","author":"Knuth D. E.","year":"1968"},{"key":"R8","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R9","unstructured":"D. W. Matula,  Selecting the  tth best in average  n+O(loglogn) comparisons, TR 73-9, Washington University, St. Louis,  1973"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Vaughan R. Pratt, Foong Frances Yao,  On lower bounds for computing the  i-th largest element,  14th Annual IEEE Symposium on Switching and Automata Theory (Univ. Iowa, Iowa City, Iowa, 1973), IEEE Comput. Soc., Northridge, Calif.,  1973,  70\u201381 57:8155","DOI":"10.1109\/SWAT.1973.18"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80029-3"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0601034"},{"key":"R13","unstructured":"M. Sobel, Technical Reports, 113, 114, Department of Statistics, University of Minnesota, Minneapolis,  1968, (Nov.)"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0211034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:41:11Z","timestamp":1787337671000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0211034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,8]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,8]]}},"alternative-id":["10.1137\/0211034"],"URL":"https:\/\/doi.org\/10.1137\/0211034","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,8]]}}}