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,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

Table of n, a(n) for n=1..13.

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

Cf. A117627, A360495.

Sequence in context: A058992 A051755 A092535 * A204662 A135667 A156624

Adjacent sequences: A215473 A215474 A215475 * A215477 A215478 A215479

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