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

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

CC BY-SA 3.0
2012-03-26T19:23:59.620Z
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}$.
David Harris
CC BY-SA 3.0
2012-03-26T17:28:31.730Z
2012-03-26T17:28:31.730Z
Mahdi Cheraghchi
<p>For instance, it is believed that for any $\epsilon&gt;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?</p>

CC BY-SA 3.0
2012-03-26T16:04:03.620Z
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 ?
Suresh Venkat
CC BY-SA 3.0
2012-03-26T16:09:16.093Z
I'm trying to ask (1). I've edited the question. Is it clearer now?
Jules
CC BY-SA 3.0
2012-03-26T16:14:47.333Z
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)$.
Jukka Suomela
CC BY-SA 3.0
2012-03-26T16:19:51.197Z
Still, that leaves a new question: are there problems for which no single asymptotically optimal algorithm exists?
Jules
CC BY-SA 3.0
2012-03-26T17:23:54.627Z
Yes, see e.g. http://blog.computationalcomplexity.org/2004/04/blum-complexity-measures.html
Sasho Nikolov
CC BY-SA 3.0
2012-03-26T18:53:42.080Z
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.
Jeffε
<cc.complexity-theory><ds.algorithms><time-complexity><matrix-product>
How can a problem have complexity $O(n^{2+\epsilon})$ for all $\epsilon > 0$?
Jules
# How can a problem have complexity $O(n^{2+\epsilon})$ for all $\epsilon > 0$?

(Asked by: username_0 on 2012-03-26)

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?

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, matrix-product

> **Comments:**
> **username_1**: 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 ?  
> **username_0**: I'm trying to ask (1). I've edited the question. Is it clearer now?  
> **username_2**: 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)$.  
> **username_0**: Still, that leaves a new question: are there problems for which no single asymptotically optimal algorithm exists?  
> **username_3**: Yes, see e.g. http://blog.computationalcomplexity.org/2004/04/blum-complexity-measures.html  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2012-03-26. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_6**: 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}$.  

---

