A215476 Minimum number of comparisons needed to find the median of n elements.

0, 1, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 23

Offset: 1

Author

Jeff Erickson, Aug 12 2012

Keywords

• nonn
• hard
• more

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)

Crossrefs

Cf. A117627, A360495.

Formula

a(n) = A360495(n,ceiling(n/2)). - Paolo Xausa, Apr 09 2023

Extensions

Added three more terms (from Kenneth Oksanen), Jeff Erickson, Aug 13 2012