Re: Idempotence and "Replication Insensitivity" are equivalent ?

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 - 19:24:45 CEST