News for hackers. Stuff that matters.
Re:Computer Scientists Make Progress on Math Puzzle by amichail on Thursday October 28, 2010 @11:30AM (#1843255)
No. For lower bounds, higher is better.
Re:Computer Scientists Make Progress on Math Puzzle by sonoffett on Thursday October 28, 2010 @01:28PM (#1843876)
Yes, higher is better because it gives you a tighter bound when searching for Big-Theta: ie. if your algorithm is in O(2^n) and the previous lower bound was Omega(n^2), and someone proves a lower bound of Omega(2^n) then you know the problem is in Theta(2^n) and you can stop looking for a faster algorithm.

It's worse in the sense that the problem takes more time to solve than if someone had found an algorithm in O(n^2).

EDIT: spelling