Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Idempotence and "Replication Insensitivity" are equivalent ?
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 - 12:16:21 CDT