-1

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

Raphael
  • 4,565
  • 28
  • 48
ocwirk
  • 135
  • 3
    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 Sep 17 '11 at 22:43
  • 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 Sep 17 '11 at 22:46
  • 1
    if they don't have an increase in time as input increases then it's easily put in O(1) – ratchet freak Sep 18 '11 at 00:49
  • 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 Sep 18 '11 at 02:13
  • 2
    related question: http://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds/ – Suresh Venkat Sep 18 '11 at 02:57
  • 3
    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 Sep 18 '11 at 03:56
  • @Kaveh could we just migrate this to math.SE? – Artem Kaznatcheev Sep 18 '11 at 12:53
  • 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 Sep 18 '11 at 13:11
  • @Rohit: Sort of. There have been many attempts to define hypercomputation, or the performance of supertasks, where, for example, the time required to complete each additional task takes half the time the preceding step required. – Aaron Sterling Sep 19 '11 at 16:12
  • @Artem, I prefer not to do it right now and wait for another close vote. – Kaveh Sep 20 '11 at 15:35
  • 2
    Though the question as stated sounds a bit naive, I think there is some interesting meat here. – Lawrence Cayton Sep 20 '11 at 16:03

2 Answers2

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

Lawrence Cayton
  • 181
  • 5
  • 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 Sep 25 '11 at 06:36
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.

Jan Johannsen
  • 4,630
  • 2
  • 33
  • 50