# Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: <pamelafluente_at_libero.it>

Date: 23 Sep 2006 10:24:45 -0700

Message-ID: <1159032285.470524.260390_at_i42g2000cwa.googlegroups.com>

Date: 23 Sep 2006 10:24:45 -0700

Message-ID: <1159032285.470524.260390_at_i42g2000cwa.googlegroups.com>

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

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 !

-P

ps

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