Complexity Theory’s 50-Year Journey to the Limits of Knowledge

Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by Dylan16807 on Saturday August 19, 2023 @12:09PM (#37190196)

Plenty of O(n), O(nlogn), O(n^2) algorithms don't strictly increase.

Rounding the decrease to the nearest time unit some of the time is hardly a disqualifier for "decreasing". (Though specifically they said "faster".)

[ Parent | on HN ]

Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by paulddraper on Saturday August 19, 2023 @12:49PM (#37190660)

Yes, but...

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.

[ Parent | on HN ]

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?

[ Parent | on HN ]