Re: Idempotence and "Replication Insensitivity" are equivalent ?

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.

> 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)?

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

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 - 15:32:25 CDT