|
No Minimum-Time Algorithm?
I was just wondering. Is there a computational problem P for which there is no asymptotically least-time solution?
In other words: let x be an algorithm which is a solution to P. Denote by T(x), the worst-case runtime of x as a function of its input size. Is it possible that for any algorithm x that solves P, there exists an algorithm y that solves P, where T(y) = o(T(x))?
o is little-o notation, so in other words that would mean T(y) = O(T(x)) and T(y) is not Θ(T(x)).
|
