Re:Computer Scientists Make Progress on Math Puzzle
by RodgerTheGreat on Thursday October 28, 2010 @11:28AM
(#1843240)
You have that backwards. An exponential bound (c^n) will massively dominate a quadratic bound (n^2). For lower bounds, smaller is better.
[ Parent
| on HN ]
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