Re: Idempotence and "Replication Insensitivity" are equivalent ?

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

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

Ok I will. As soon as I have finished some urgent work.

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

clearly just missed to type n, I think I have never seen O(log n) in my programming of aggregate functions, or I didn't note they are ...

BTW, I am curious: what are examples of O(log n) aggregate functions in DBMS theory ?

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

myself, I guess :))

>
>
> Marshall
Received on Thu Sep 21 2006 - 12:22:02 CEST