Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: <>
Date: 23 Sep 2006 10:24:45 -0700
Message-ID: <>

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.


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

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.

What a "tortoise" function !


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

> Marshall
Received on Sat Sep 23 2006 - 19:24:45 CEST

Original text of this message