Median

[Marcin]

How I can find median (middle element) in T(n) = O(n) int the worst case?

 

[CBFalconer]

How I can find median (middle element) in T(n) = O(n) int the
worst case?

By asking in a newsgroup where it is topical, such as
comp.programming. You probably won't like the answer.

 

[Markus Moll]

Hi

How I can find median (middle element) in T(n) = O(n) int the worst case?

Off-Topic, but google for "selection algorithm", "kth element O(n)".
Or have a look here: http://www.ics.uci.edu/~eppstein/161/960130.html.

Be aware though that the algorithm performs worse than sorting in O(n log n)
for reasonable amounts of data.

Markus

 

[BGreene]

How I can find median (middle element) in T(n) = O(n) int the worst case?

This depends on what O(n) means, comparisons, moves, passes over the data
etc...

I think you are impying comparisons, in which case it cannot be done.

 

[Richard Harter]

This depends on what O(n) means, comparisons, moves, passes over the data
etc...

I think you are impying comparisons, in which case it cannot be done.

As it happens the subject is off topic and your reply is incorrect;
the median can be found using worst case O(n) comparisons.



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

 

[Daniel Etzold]

As it happens the subject is off topic and your reply is incorrect;
the median can be found using worst case O(n) comparisons.

btw, each deterministic algorithm requires at least 2n
comparisons in worst case to find the median (currently the best known
requires det. alg. requires about 2.95n comparisons).
A very simple randomized algorithm finds the median with at most
1.5n + o(n) comparisons with prob. 1-n^(1/4).

Regards,
Daniel

 

[BGreene]

I apologize for this ignorant post. I was thinking n comparsions not O(n).
Next time I'll keep my keyboard quiet .

Barry

 

[pete]

I apologize for this ignorant post.
I was thinking n comparsions not O(n).
Next time I'll keep my keyboard quiet .

Big O refers to the dominant term
of the equation which governs the running time.

 

[Richard Harter]

I apologize for this ignorant post. I was thinking n comparsions not O(n).
Next time I'll keep my keyboard quiet .

No problem. It's not at all obvious (until you think of the trick)
that it can be done in guaranteed O(n) comparisons. The best
published algorithms involve dancing widdershins and flapping your
arms chicken style.


Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.