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.
[ Parent
| on HN ]
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