Is it possible that time complexity of any algorithm decreases as the input size increases, are there any examples

Question

I just read in Cormen's algorithm book that big-O and big-omega do not follow the trichotomy property. That means for two functions, $f(n)$ and $g(n)$, it may be the case that neither $f(n) = O(g(n))$ nor $f(n) = \Omega(g(n))$ holds. In example they argue that if function is $n^{1+\sin(n)}$ than it is possible.

While this is correct, is it possible in a real world algorithm to have a run time of something like $\sin(n)$? Since it would sometimes decrease, with the increase of input size. Does anybody know of any such algorithm or can give a small code snippet which does this?

If it is not possible, then is it correct to assume that Given a problem P with size $n$, if it can not be solved in $O(f(n))$ time by any known algorithm, then the lower bound of P is $\Omega(f(n))$.

Answer 1

Actually, there is a really interesting example of a real-world algorithm whose running time decreases with increasing input size: Support Vector Machine (SVM) training using a (specific) stochastic gradient descent approach.

In SVM training, we are after a classifier (linear in this work) that attains a certain error rate. That error rate depends both on (1) the approximation error, (2) the estimation error, and (3) on the optimization error. (1) has to do with the richness of the function class---what's the best that a (say) linear function can do on this particular input distribution? (2) has to do with the difference between measuring error on the training set and measuring error on the real distribution (or a test set). (3) has to do with how well the optimization problem is solved---in general, you cannot get a zero-cost solution on the training data.

As more training data is available (ie the input size increases), the estimation error decreases. In other words, there is less of a difference between the empirical and true error. So to get the same overall error level, we can actually increase the amount of acceptable optimization error. Interestingly, the overall effect is a net gain: one can actually run the training procedure for less time with more data.

The specific algorithm is called PEGASOS and their nice paper demonstrates this effect theoretically and with experiments. See in particular eq (10) of

Shai Shalev-Shwartz and Nathan Srebro. SVM Optimization: Inverse Dependence on Training Set Size. ICML 2008.

(Note: I kept this discussion at a very high level since the details are a bit subtle to someone without a machine learning background.)

Answer 2

A classic example would be Euclid's algorithm for computing the gcd. Its running time has peaks when the inputs are consecutive Fibonacci numbers, but can become smaller again as, say, the larger input is increased. Consider e.g. gcd(34,21), where the computation requires 8 iterations, vs. gcd(35,21), where the computation takes only 4 iterations.