For instance, it is believed that for any $\epsilon>0$ there is an algorithm for matrix multiplication that runs in $O(n^{2+\epsilon})$, but possibly no algorithm that runs in $O(n^2)$. How is this possible? Couldn't we create a meta-algorithm that runs in $O(n^2)$ time by using a better and better algorithm to solve problems of bigger size?

  • 4
    $\begingroup$ There seem to be two questions here: (1) how can you have an algorithm for a problem with running time $n^{c+\epsilon}$ and (2) how can matrix multiplication admit such a method. Which one is it ? $\endgroup$ Mar 26 '12 at 16:04
  • $\begingroup$ I'm trying to ask (1). I've edited the question. Is it clearer now? $\endgroup$
    – Jules
    Mar 26 '12 at 16:09
  • 13
    $\begingroup$ There is a comparison-based sorting algorithm with complexity $O(n^{1+\epsilon})$ for all $\epsilon > 0$, but there is no such algorithm with complexity $O(n)$. $\endgroup$ Mar 26 '12 at 16:14
  • 2
    $\begingroup$ Yes, see e.g. blog.computationalcomplexity.org/2004/04/… $\endgroup$ Mar 26 '12 at 17:23
  • 4
    $\begingroup$ Usually that notation means that the constant hidden by the big-Oh notation depends on ε (and diverges as ε goes to zero). Moreover, either the dependence is too complicated to solve for the best value of ε, or the author was too lazy to try. $\endgroup$
    – Jeffε
    Mar 26 '12 at 18:53

In this case, it's another way of saying that the algorithm runs in time $O(n^{2+o(1)})$; for example $O(n^2 \log^6 n)$ or $O(n^2 2^{\sqrt{\log n}})$ would both qualify.

Sometimes there are parameters other than the running time involved in an algorithm, for example quality of an approximation, that depend on $\epsilon$. In such cases, an algorithm may be designed to accept a parameter $\epsilon$ as a part of the input and adjust its performance accordingly.

  • 5
    $\begingroup$ This is not necessarily equivalent. Having a single algorithm in time $n^{2+o(1)}$ is a stronger condition than having infinitely many separate algorithms (which may not be computable) with running time $n^{2+\epsilon}$. $\endgroup$ Mar 26 '12 at 19:23

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.