News for hackers. Stuff that matters.
Re:Computer Scientists Make Progress on Math Puzzle by rix0r on Thursday October 28, 2010 @11:31AM (#1843263)
Well, a quadratic lower bound is better than an exponential lower bound, in the sense that the problem could still turn out to not be in EXPTIME but in PTIME.

It is worse in the sense that it tells us less about the actual complexity class the problem is in, so I guess it depends on what you interpret "better" to mean in this context.

Re:Computer Scientists Make Progress on Math Puzzle by amichail on Thursday October 28, 2010 @11:34AM (#1843277)
You could always say the lower bound is zero or some very small function. That's pointless and is not better in any sense.
Re:Computer Scientists Make Progress on Math Puzzle by cma on Thursday October 28, 2010 @12:19PM (#1843504)
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

Re:Computer Scientists Make Progress on Math Puzzle by sonoffett on Thursday October 28, 2010 @01:12PM (#1843780)
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

Re:Computer Scientists Make Progress on Math Puzzle by cma on Thursday October 28, 2010 @07:52PM (#1845464)
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