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?)

  • 3
    $\begingroup$ Could you describe this a bit better? We can't do every pairwise comparison, obviously, because that's quadratic time. $\endgroup$ – Eli Feb 26 '11 at 18:24
  • 3
    $\begingroup$ @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 . . ." $\endgroup$ – jbapple Feb 26 '11 at 21:08
  • $\begingroup$ @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 $\endgroup$ – Ellie Kesselman Jul 23 '11 at 2:52
  • $\begingroup$ @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= $\endgroup$ – jbapple Jul 23 '11 at 3:34
  • $\begingroup$ @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. $\endgroup$ – Ellie Kesselman Jul 23 '11 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.