login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215476 Minimum number of comparisons needed to find the median of n elements. 0
0, 1, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 23 (list; graph; refs; listen; history; text; internal format)
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.

W. Gasarch, W. Kelly, and W. Pugh, Finding the ith largest of n for small i,n, SIGACT News 27(2):88-96, 1996.

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Sect. 5.3.2.

K. Okansen, Searching for selection algorithms, Elec. Notes Discrete Math. 27:77, 2006.

LINKS

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

K. Okansen, Selecting the i'th largest of n elements. (last modified April 2005)

CROSSREFS

Cf. A117627.

Sequence in context: A058992 A051755 A092535 * A204662 A135667 A156624

Adjacent sequences:  A215473 A215474 A215475 * A215477 A215478 A215479

KEYWORD

nonn,hard

AUTHOR

Jeff Erickson, Aug 12 2012

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 04:44 EDT 2019. Contains 324217 sequences. (Running on oeis4.)