Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Marshall <>
Date: 23 Sep 2006 10:43:03 -0700
Message-ID: <> wrote:
> Marshall ha scritto:
> > 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.
> Really?

Notice the smarmy and inflammatory "Really?". Note the lack of any actual attempt to address the point I made, which was that he pointed at an O(n logn) function and called it linear. Troll.

> Just like the fact that the theoretical bound
> for median computation is 2n.

Note the irrelevant introduction of different, related point, to distract from the fact that he pointed at an O(n logn) function and callled it linear. Troll.

> Oh right that just "theorical", Dor and Zwick, poor guys, only succeed
> in a very slow implementation of computational complexity equal to
> 2.95 n.

Note the irrelevant introduction of a completely different function, distinct from the various other ones he has mentioned up to now, in an attempt to distract from the actual point, which was that he mistakenly identified a O(n logn) function as linear. Troll. Note that there is no indication so far in this thread that he even understands what Big O actually means. In fact he implies that my definition is incorrect.

> D. Dor and U. Zwick. Selecting the median.
> Proc. Sixth ACM-SIAM Symp.
> Discrete Algorithms (SODA), pages 28-37, 1995.

Notice the distracting tactic of appeal to authority, even though there is nothing to indicate that this paper has anything to do with the algorithm that he pointed at earlier. Troll.

Also: man.

Marshall Received on Sat Sep 23 2006 - 19:43:03 CEST

Original text of this message