Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Marshall <marshall.spight_at_gmail.com>
Date: 23 Sep 2006 10:16:21 -0700
Message-ID: <1159031781.503355.39680_at_d34g2000cwd.googlegroups.com>


pamelafluente_at_libero.it wrote:
> Marshall ha scritto:
>
> > pamelafluente_at_libero.it wrote:
> > >
> > > Median can be computed O(n) like mean.
> > That page describes an algorithm that is O(n logn). Just because that
> > pages *says* the algorithm is linear doesn't mean that the algorithm
> > actually is linear.
>
> see
> http://en.wikipedia.org/wiki/Median#Efficient_computation

That page says that there exists an O(n) median algorithm. It does not say anything about the earier algorithm you posted, which remains O(n logn). Its typical runtime is linear, but Big O is not a measure of typical runtime; it's a measure of worst-case.

Marshall Received on Sat Sep 23 2006 - 19:16:21 CEST

Original text of this message