<p>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.</p>

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

<blockquote>
  <p>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.</p>
</blockquote>

<p>One can also look at other selection problems, element distinctness, sorting,
and other such problems.</p>

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

CC BY-SA 3.0
2011-07-23T02:52:42.283Z
@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 K
CC BY-SA 3.0
2011-07-23T03:34:09.180Z
@Feral Oink - It was just a link to the Google Scholar search for the paper "On lower bounds for selecting the median". http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1412
jbapple
CC BY-SA 3.0
2011-07-23T03:36:26.160Z
@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 K
CC BY-SA 2.5
2011-02-26T18:24:25.317Z
Could you describe this a bit better? We can't do every pairwise comparison, obviously, because that's quadratic time.
Eli
CC BY-SA 2.5
2011-02-26T21:08:28.797Z
@Eli - Maybe GASARCH means the definition from "On lower bounds for selecting the median" (http://scholar.google.com/scholar?cluster=10317167134453583556), that is: ". . . algorithm that starts by comparing \floor{n/2} disjoint pairs of elements . . ."
jbapple
<cc.complexity-theory><lower-bounds><time-complexity><sorting>
For median is it optimal to compare in pairs first?
Bill GASARCH
# For median is it optimal to compare in pairs first?

(Asked by: username_0 on 2011-02-26)

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

**Tags:** cc.complexity-theory, lower-bounds, time-complexity, sorting

> **Comments:**
> **username_3**: Could you describe this a bit better? We can't do every pairwise comparison, obviously, because that's quadratic time.  
> **username_2**: @username_3 - Maybe GASARCH means the definition from "On lower bounds for selecting the median" (http://scholar.google.com/scholar?cluster=10317167134453583556), that is: ". . . algorithm that starts by comparing \floor{n/2} disjoint pairs of elements . . ."  
> **username_1**: @username_2 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  
> **username_2**: @Feral Oink - It was just a link to the Google Scholar search for the paper "On lower bounds for selecting the median". http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1412  
> **username_1**: @username_2 Oh! Okay! Thank you. That is so much more familiar to me, CiteSeerX and of course DOI. Much appreciated. I clicked, all was well.  

---

## 0 answers

