Median

[Marcin]

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

--

Marcin

[CBFalconer]

Re: Median

Marcin wrote:[color=blue]
>
> How I can find median (middle element) in T(n) = O(n) int the
> worst case?[/color]

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

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Markus Moll]

Re: Median

Hi

Marcin wrote:
[color=blue]
> How I can find median (middle element) in T(n) = O(n) int the worst case?[/color]

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]

Re: Median


"Marcin" <seemann19@o2.p l> wrote in message
news:d3amqd$636 $1@news.dialog. net.pl...[color=blue]
> How I can find median (middle element) in T(n) = O(n) int the worst case?
>
> --
>
> Marcin
>
>[/color]
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]

Re: Median

On Fri, 15 Apr 2005 23:16:50 -0500, "BGreene" <barryg@highstr eam.net>
wrote:
[color=blue]
>
>"Marcin" <seemann19@o2.p l> wrote in message
>news:d3amqd$63 6$1@news.dialog .net.pl...[color=green]
>> How I can find median (middle element) in T(n) = O(n) int the worst case?
>>
>> --
>>
>> Marcin
>>
>>[/color]
>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.[/color]

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, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Daniel Etzold]

Re: Median

Richard Harter wrote:[color=blue]
> On Fri, 15 Apr 2005 23:16:50 -0500, "BGreene" <barryg@highstr eam.net>
> wrote:
>
>[color=green]
>>"Marcin" <seemann19@o2.p l> wrote in message
>>news:d3amqd$6 36$1@news.dialo g.net.pl...
>>[color=darkred]
>>>How I can find median (middle element) in T(n) = O(n) int the worst case?
>>>
>>>--
>>>
>>>Marcin
>>>
>>>[/color]
>>
>>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.[/color]
>
>
> As it happens the subject is off topic and your reply is incorrect;
> the median can be found using worst case O(n) comparisons.
>[/color]

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
[color=blue]
>
>
> Richard Harter, cri@tiac.net
> http://home.tiac.net/~cri, http://www.varinoma.com
> Save the Earth now!!
> It's the only planet with chocolate.[/color]

[BGreene]

Re: Median

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

Barry

"BGreene" <barryg@highstr eam.net> wrote in message
news:11614irajh oj3eb@corp.supe rnews.com...[color=blue]
>
> "Marcin" <seemann19@o2.p l> wrote in message
> news:d3amqd$636 $1@news.dialog. net.pl...[color=green]
> > How I can find median (middle element) in T(n) = O(n) int the worst[/color][/color]
case?[color=blue][color=green]
> >
> > --
> >
> > Marcin
> >
> >[/color]
> 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.
>
>[/color]

[pete]

Re: Median

BGreene wrote:[color=blue]
>
> I apologize for this ignorant post.
> I was thinking n comparsions not O(n).
> Next time I'll keep my keyboard quiet :-).[/color]
[color=blue][color=green]
> > 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.[/color][/color]

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

--
pete

[Richard Harter]

Re: Median

On Thu, 28 Apr 2005 12:28:57 -0500, "BGreene" <barryg@highstr eam.net>
wrote:
[color=blue]
>I apologize for this ignorant post. I was thinking n comparsions not O(n).
>Next time I'll keep my keyboard quiet :-).[/color]

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, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.