Re: problem on medians

Richard Heathfield wrote:
CBFalconer said:
Richard Heathfield wrote:
ak said:

what are the least no. of comparisons to find the medain of a set
of n integers ?

I presume you mean "median".

The answer is of course 0, which occurs when n is 0, 1, or 2. For
n = 0, there is nothing to compare, so no comparisons can occur.
When n is 1, there is only one value, which is its own median, so
no comparison is required. When n is 2, the median is given by the
sum of the two elements divided by 2, and again no comparison is
required.

Harumph. He didn't say "set of n non-negative integers". :-)

I didn't say he did. But n itself must be non-negative - or are you
claiming that you can have a set of integers that has fewer than no
members?

I am claiming that the 'set of integers' can have negative
members. On re-reading, maybe I jumped the gun.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: sliding median filter
    ... >>for a data set, x, of length m, create data set, y, ... >>and not be calculating the median from scratch. ... As members are added to the set, ... This approach is likely to be fast, and there is no need to sort ...
    (comp.programming)
  • Re: <?????Nora Baron???????>
    ... that the median is $44,186 and the average is $25,491. ... Let X be the average salary in the first set, ... That would mean that salaries are mostly either just very slightly above ...
    (sci.math)
  • Re: sliding median filter
    ... > for a data set, x, of length m, create data set, y, ... > For example, when I calculate y_i, I find the median of some set. ... As members are added to the set, ... This approach is likely to be fast, and there is no need to sort ...
    (comp.programming)
  • Re: Am I missing something or is this algorithm NlogN , not linear?
    ... >>> I don't think anyone is claiming that it's too hard to implement, ... > where cn is the number of comparisons to find the median of 5 ... > Note that Blum, et al also gave an "optimized" version of their ... > median-of-medians algorithm with 5.43n comparisons. ...
    (comp.theory)
  • Re: Who goes bare?
    ... CCBN (and its officers) should not be claiming that there is any advantage to hiding from view, parts of ones anatomy. ... majority of members! ...
    (uk.rec.naturist)