# 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>

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