Re: Idempotence and "Replication Insensitivity" are equivalent ?

Marshall <marshall.spight_at_gmail.com> wrote:
> 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.

So I decided to become informed on this. There is an algorithm for worst-case O(n) performance in computing a median. However, it is generally agreed not to be practical because of the high constant multiple in managing the complex data structures involved. There is a far simpler randomized algorithm for computing the median in time that is worst case O(n log n) and average case O(n).

Oh, and just a pet peeve of mine... big-O notation does not refer to worst case time bound, although that is an extremely common mis-use of the term. Big-O is a characterization of a function rather than an algorithm, and functions do not have a best case or worst case value; they just have one value for any given n. Big O means that the actual, specific value of the function is less than or equal to some constant times some other function of n (for all n \geq n_0). If the function you are trying to characterize is the worst case running time for some algorithm, then it's up to you to say that, imply it from context, or let it be assumed (as it generally is). It's also quite possible to use big-O notation to characterize average run time, amortized worst case run time for a repeated algorithm, or even best case performance (in which it would mean: for any n, there exists some possible input of size n so that the algorithm will run in no longer than a constant times g(n) time).

-- 
Chris Smith