[Dylan16807]

"Faster as the input grows" is perfectly compatible with a minimum number of time units. If your definition insists the minimum of time units must be 0, with infinitesimal time getting involved, then your definition sucks.

[paulddraper]

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]

Strictly speaking it either tends to negative infinity, or tends to so real number X, which could be any number positive or negative.

[paulddraper]

In that latter case, statement 1 is true.

[Dylan16807]

3. Nobody said "strictly".

[paulddraper]

They said decreases, not stays constant

[Dylan16807]

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

[paulddraper]

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.

[Dylan16807]

> 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?