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@i42g2000cwa.googlegroups.com>

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?

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 - 12:24:45 CDT