Re: Idempotence and "Replication Insensitivity" are equivalent ?

"Marshall" <marshall.spight_at_gmail.com> wrote in message news:1158784344.939265.89060_at_e3g2000cwe.googlegroups.com...
> pamelafluente_at_libero.it wrote:
> >
> > Median can be computed O(n) like mean.
> > e.g.
> >
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
>
> 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.
>
>

You are right. It's O(n*log(n)).

The author of the page didn't count on the average depth of recursion verying like log (n).

> > Further, memory is a problem, I could show you at least one algorithm
> > which
> > compute the median on a stream of data (no need to sort them)
>
> Please do! Although I note that nothing about stream algorithms limits
> them to any bounds of memory or computation time, so just saying
> it's a stream algorithm doesn't tell us anything useful.
>
>
> > If it takes O(log n) instead of O(n) and the user is willing
> > to wait a little more because he needs that result, what are you going
> > to do ? (Of course, I agree, forget about quadratic complexity, I
> > didn't
> > reach that far)
>
> So it is your belief that O(log n) is slower than O(n)?
>
>

Let's be careful here. O(n*log (n)) is slower than O(n).

O(log(n)) is faster than O(n).

Details, details.

> > I find a little weird that some db experts are not familiar with
> > computational complexity of the most common functions.
>

I wonder who he's talking about?
> Of whom do you speak? Your concern is ironic given that
> you've made three errors in bounding complexity just in
> this one quoted post.
>
>
> Marshall
>
Received on Wed Sep 20 2006 - 23:40:41 CEST