# For median is it optimal to compare in pairs first?

Median can be done in linear time and is now down to (I think) $2.97n$. The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small.

The following theorem, if true, may help improve lower bounds in general and upper bounds for particular small values of $n$:

If MEDIAN of $n$ elements can be found in $f(n)$ comparisons (worst case) then there is an algorithm taking $f(n)$ (perhaps $f(n) + O(1)$) that initially compares all of the elements in pairs.

One can also look at other selection problems, element distinctness, sorting, and other such problems.

(Meta Question - I couldn't find a good tag for this so I used lower-bounds. Is there a better one that I missed?)

• Could you describe this a bit better? We can't do every pairwise comparison, obviously, because that's quadratic time. – Eli Feb 26 '11 at 18:24
• @Eli - Maybe GASARCH means the definition from "On lower bounds for selecting the median" (scholar.google.com/scholar?cluster=10317167134453583556), that is: ". . . algorithm that starts by comparing \floor{n/2} disjoint pairs of elements . . ." – jbapple Feb 26 '11 at 21:08
• @jbapple That link to Google Scholar doesn't work anymore. I tried entering by typing in, searching a bit on key words, no luck. Could you provide source info, or update the link maybe? Thanks – Ellie Kesselman Jul 23 '11 at 2:52
• @Feral Oink - It was just a link to the Google Scholar search for the paper "On lower bounds for selecting the median". citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1412 – jbapple Jul 23 '11 at 3:34
• @jbapple Oh! Okay! Thank you. That is so much more familiar to me, CiteSeerX and of course DOI. Much appreciated. I clicked, all was well. – Ellie Kesselman Jul 23 '11 at 3:36