2 ms·
For a function to strictly decrease forever, at least one of two statements is true: 1. It decreases by vanishingly smaller amount. 2. It decreases to negativ
by paulddraper 3y ago
For a function to strictly decrease forever, at least one of two statements is true:
1. It decreases by vanishingly smaller amount.
2. It decreases to negative infinity.
So...which is it? Infinitesimal time units, or negative time?
- quickthrower2 3y agoStrictly speaking it either tends to negative infinity, or tends to so real number X, which could be any number positive or negative.
- paulddraper 3y agoIn that latter case, statement 1 is true.
- Dylan16807 3y ago3. Nobody said "strictly".
- paulddraper 3y agoThey said decreases, not stays constant
- Dylan16807 3y agoPlenty 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".)
- paulddraper 3y agoYes, 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.
- Dylan16807 3y ago> 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?