4 ms·
You have that backwards. An exponential bound (c^n) will massively dominate a quadratic bound (n^2). For lower bounds, smaller is better.
by RodgerTheGreat 16y ago
You have that backwards. An exponential bound (c^n) will massively dominate a quadratic bound (n^2). For lower bounds, smaller is better.
- amichail 16y agoNo. For lower bounds, higher is better.
- sonoffett 16y agoYes, 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