Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?

Question

Suppose that, for each $\epsilon > 0$, there is an Turing machine $M_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a + o(1)})$? (Here, the $o(1)$ term is measured in terms of $n$, the input length.)

Does it make a difference if the algorithms $M_{\epsilon}$ are computable, or efficiently computable, in terms of $\epsilon$?

Motivation: in many proofs, it is easier to construct algorithms of time $O(n^{a + \epsilon})$ than the limiting algorithm $O(n^{a + o(1)})$. In particular, you need to bound the constant term in $O(n^{a + \epsilon})$ to pass to the limit $O(n^{a+o(1)})$. It would be nice if there is some general result you can invoke to pass to the limit directly.

Answer 1

The question is similar to the questions about constructive existence of the limit of a sequence of (constructive) objects. Usually if you can uniformly construct those objects (here $M\epsilon$) efficiently enough then you can show the existence of the limit constructively.

For example, assume that we have a TM $N(k,x)$ which runs $M_{|k|^{-1}}$ on $x$ and its running time is $O(n^{a+|k|^{-1}})+O(|k|)$ (here the bounds are also uniform, e.g. something like $O(2^k.n^{a+|k|^{-1}})$ would not work). Then we can combine this uniform simulator with the function $(k,x)\mapsto x$ to obtain the machine $N(x,x)$ that runs in time $O(n^{a+o(1)})$.

PS: $O(n^{a+o(1)})$ is a little bit ambiguous because of nesting of asymptotic notations, I am interpreting it as $n^{a+o(1)}$. Also we need $a$ to be not too small, e.g. at least $1$.

Answer 2

You can use Levin's universal search algorithm. Suppose that you can somehow enumerate a sequence of algorithms $A_k$ deciding $L$, each running in time $C_k n^{a+1/k}$. Levin's algorithm runs in time $T(n) \leq D_k n^{a+1/k}$ for every $k$, where $D_k$ is a constant depending on $C_k$. So for every $k$, $$ \tau(n) \triangleq \frac{\log T(n)}{\log n} - a \leq \frac{\log D_k + (a+1/k) \log n}{\log n} - a = \frac{\log D_k}{\log n} + \frac{1}{k}. $$ Given $\epsilon>0$, choose $k = \lceil 2/\epsilon \rceil$, and let $N = \lceil D_k^{2/\epsilon} \rceil$. Then for $n \geq N$, $\tau(n) \leq \epsilon$. Therefore $\tau(n) \rightarrow 0$, and we get that Levin's algorithm runs in time $n^{a+\tau(n)} = n^{a+o(1)}$.