OFFSET
1,3
COMMENTS
Dor and Zwick 1999 prove a(n) <= 2.95n + o(n).
Dor and Zwick 2001 prove a(n) >= (2+2^(-80))n - o(n).
REFERENCES
D. Dor and U. Zwick, Median selection requires (2+epsilon)n comparisons, SIAM J. Discrete Math 14(3):312-325, 2001.
D. Dor and U. Zwick, Selecting the median, SIAM J. Comput. 28(5):1722-1758, 1999.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Sect. 5.3.2.
Kenneth Oksanen, Searching for selection algorithms, Elec. Notes Discrete Math. 27:77, 2006.
LINKS
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.
Kenneth Oksanen, Selecting the i'th largest of n elements. (last modified April 2005)
FORMULA
a(n) = A360495(n,ceiling(n/2)). - Paolo Xausa, Apr 09 2023
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Jeff Erickson, Aug 12 2012
EXTENSIONS
Added three more terms (from Kenneth Oksanen), Jeff Erickson, Aug 13 2012
STATUS
approved