On: Computer Scientists Make Progress on Math Puzzle

[cma]

There are two notions of lower bound:

lower bound like you are talking about (the function always takes longer than this to run for an input of size n)

lower bound across all inputs of size n (the function never runs faster than this, given any possible input of size n)

The two are different

[sonoffett → cma]

I'm pretty sure your second definition is an upper bound (big-O) and the first definition is a lower bound (big-Omega).

EDIT: adding a link to the wikipedia article defining Big-O and Big-Omega: http://en.wikipedia.org/wiki/Big_O_notation

[cma → sonoffett]

Yeah I screwed that up, what I meant to refer to is this:

    >It is not contradictory however, to say that the worst-case
    >running time of insertion sort is [Big Omega](n^2),
    >since there exists an input that causes the algorithm
    >to take [Big Omega](n^2) time.
    >Introduction to Algorithms, 2nd Edition, p 46