<p>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. </p>

CC BY-SA 3.0
2011-09-21T14:23:09.877Z
2011-09-21T14:23:09.877Z
Jan Johannsen
<p>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.  </p>

<p>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.  </p>

<p>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.  </p>

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

<p>Shai Shalev-Shwartz and Nathan Srebro.  <a href="http://ttic.uchicago.edu/~nati/Publications/SSSICML08.pdf">SVM Optimization: Inverse Dependence on Training Set Size</a>.  ICML 2008.</p>

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

CC BY-SA 3.0
2011-09-25T06:36:16.790Z
`As more training data is available (ie the input size increases), the estimation error decreases.` Does the estimation error influence the running time of the algorithm? Your answer reads to me like as input size increases the optimization provides a better answer. It does not sound like as input size increases, the training algorithm complexity decreases.
goldsz
CC BY-SA 3.0
2011-09-20T14:28:37.313Z
2011-09-20T14:28:37.313Z
Lawrence Cayton
<p>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.</p>

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

<p>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))$.</p>

CC BY-SA 3.0
2011-09-17T22:43:09.080Z
The lower bound of the complexity of a problem is something more than “it cannot be solved in such and such time by any known algorithm.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T22:46:18.797Z
It is possible for problems to not have a time complexity. I.e., There is no algorithm $M$ which attains the lower bound on running times of algorithms $M'$ deciding $L$. For example, the decision procedure for the theory WS1S does not have time complexity.
David Harris
CC BY-SA 3.0
2011-09-18T00:49:23.167Z
if they don't have an increase in time as input increases then it's easily put in O(1)
ratchet freak
CC BY-SA 3.0
2011-09-18T02:13:56.053Z
an algorithm with oscillating running time: The input is a binary integer. if it is divisible by two (testable in $O(\log n)$ time), then do nothing. else, run some algorithm that takes $O(2^n)$ time.
Chao Xu
CC BY-SA 3.0
2011-09-18T02:57:41.343Z
related question: http://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds/
Suresh Venkat
CC BY-SA 3.0
2011-09-18T03:56:23.310Z
This doesn't seem to be a research-level question and therefore is off-topic on cstheory, please read the FAQ to understand the scope of the site. You can try asking it on Math.SE.
Kaveh
CC BY-SA 3.0
2011-09-18T12:53:46.020Z
@Kaveh could we just migrate this to math.SE?
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-18T13:11:27.967Z
There certainly are algorithms with non-monotone runtimes, even though they are rarely analyzed that closely. The given function is not really a counterexample as in the realm of computability, we always have discrete input sizes and therefore no poles; local maxima can be dominated by any other function times a suitable constant.
Raphael
CC BY-SA 3.0
2011-09-19T16:12:32.027Z
@Rohit: Sort of.  There have been many attempts to define [hypercomputation](http://en.wikipedia.org/wiki/Hypercomputation), or the performance of [supertasks](http://en.wikipedia.org/wiki/Supertask), where, for example, the time required to complete each additional task takes half the time the preceding step required.
Aaron Sterling
CC BY-SA 3.0
2011-09-20T15:35:10.767Z
@Artem, I prefer not to do it right now and wait for another close vote.
Kaveh
CC BY-SA 3.0
2011-09-20T16:03:35.263Z
Though the question as stated sounds a bit naive, I think there is some interesting meat here.
Lawrence Cayton
<ds.algorithms>
Is it possible that time complexity of any algorithm decreases as the input size increases, are there any examples
ocwirk
# Is it possible that time complexity of any algorithm decreases as the input size increases, are there any examples

(Asked by: username_0 on 2011-09-17)

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

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: The lower bound of the complexity of a problem is something more than “it cannot be solved in such and such time by any known algorithm.”  
> **username_2**: It is possible for problems to not have a time complexity. I.e., There is no algorithm $M$ which attains the lower bound on running times of algorithms $M'$ deciding $L$. For example, the decision procedure for the theory WS1S does not have time complexity.  
> **username_3**: if they don't have an increase in time as input increases then it's easily put in O(1)  
> **username_4**: an algorithm with oscillating running time: The input is a binary integer. if it is divisible by two (testable in $O(\log n)$ time), then do nothing. else, run some algorithm that takes $O(2^n)$ time.  
> **username_5**: related question: http://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds/  
> **username_6**: This doesn't seem to be a research-level question and therefore is off-topic on cstheory, please read the FAQ to understand the scope of the site. You can try asking it on Math.SE.  
> **username_7**: @username_6 could we just migrate this to math.SE?  
> **username_8**: There certainly are algorithms with non-monotone runtimes, even though they are rarely analyzed that closely. The given function is not really a counterexample as in the realm of computability, we always have discrete input sizes and therefore no poles; local maxima can be dominated by any other function times a suitable constant.  
> **username_9**: @Rohit: Sort of.  There have been many attempts to define [hypercomputation](http://en.wikipedia.org/wiki/Hypercomputation), or the performance of [supertasks](http://en.wikipedia.org/wiki/Supertask), where, for example, the time required to complete each additional task takes half the time the preceding step required.  
> **username_6**: @Artem, I prefer not to do it right now and wait for another close vote.  
> **username_10**: Though the question as stated sounds a bit naive, I think there is some interesting meat here.  

---

## 2 answers

### Answer by username_11 on 2011-09-21. Score: 5

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.


---

### Answer by username_10 on 2011-09-20. Score: 5

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](http://ttic.uchicago.edu/~nati/Publications/SSSICML08.pdf). 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.)

> **Comments:**
> **username_12**: `As more training data is available (ie the input size increases), the estimation error decreases.` Does the estimation error influence the running time of the algorithm? Your answer reads to me like as input size increases the optimization provides a better answer. It does not sound like as input size increases, the training algorithm complexity decreases.  

---

