Re:Complexity Theory’s 50-Year Journey to the Limits of Know...
by Dylan16807 on Saturday August 19, 2023 @01:37PM
(#37191135)
> The mathematically rigorous form of the posed question is whether there is an algorithm with run time f(N) for which there exists strictly decreasing g(N) such that f(N) = O(g(N)). That is, the run time is bounded by a forever decreasing function.
Let's say my minimum runtime is 7, and the strictly decreasing bound on my runtime is g(N) = 1e15/N + 7
Doesn't that fit your description fine?
The mathematically rigorous form of the posed question is whether there is an algorithm with run time f(N) for which there exists strictly decreasing g(N) such that f(N) = O(g(N)). That is, the run time is bounded by a forever decreasing function.
f(N) itself doesn't need to be strictly decreasing, but there needs to be a g(N) that is.
Bottom line, no algorithm can have a forever decreasing run time as N increases. An algorithm can exhibit that behavior over a limited range of N, but that's not how complexity works.