-1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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.” $\endgroup$ – Tsuyoshi Ito Sep 17 '11 at 22:43
  • 1
    $\begingroup$ if they don't have an increase in time as input increases then it's easily put in O(1) $\endgroup$ – ratchet freak Sep 18 '11 at 0:49
  • 2
    $\begingroup$ related question: cstheory.stackexchange.com/questions/5553/… $\endgroup$ – Suresh Venkat Sep 18 '11 at 2:57
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh Sep 18 '11 at 3:56
  • 2
    $\begingroup$ Though the question as stated sounds a bit naive, I think there is some interesting meat here. $\endgroup$ – Lawrence Cayton Sep 20 '11 at 16:03
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – goldsz Sep 25 '11 at 6:36
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.