- #1

- 315

- 1

## Main Question or Discussion Point

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)).

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)).