# Do there exist any problems with optimal algorithms beyond $O(n)$?

Blum's Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other words, does there exist a language $$L$$ which is decided by some algorithm within $$f(n)$$ steps so that any other algorithm which solves the same problem also runs in $$\Omega(f(n))$$ steps? If $$f$$ is linear, this is trivially the case. But what about beyond linear? Just a nonconstructive existence proof would already be cool.

(Deterministic) TMs with a single tape can recognize palindromes in time $$O(n^2)$$. It has been proven that this time bound is optimal (see, e.g., this paper).
• The first paper you cite seems to only prove its results under severe restrictions. I was hoping for something more general, ideally even encompassing nondeterministic machines. As for the time hierarchy theorems, they only give problems not in $O(f(n))$ for arbitrary $f$. But that doesn't mean that those problems actually have a fastest algorithm. Aug 7, 2019 at 14:22
• @SebastianOberhoff Also, I do not quite understand what you mean by the time hierarchy theorems not being relevant. They give an explicit construction of a language which can be decided in time $f(n)$ but not in time $g(n)$ for any $g \in o(f)$ (at least for NTMs; the DTM version does not qualify because of the $\log n$ slack factor). Aug 7, 2019 at 14:30
• That's a slight misstatement of the nondeterministic time hierarchy. a) there's a little +1 flying around in the exact statement of the theorem. b) We get a different language for every pair of functions $f, g$ rather than a single language that works for all $g$ "smaller than" $f$. Aug 7, 2019 at 14:51
• @SebastianOberhoff No, we do not quantify over pairs of $f$ and $g$. We have a fixed $f$ and the language is recognizable in time $f$. Then, for any $g$ with $g(n+1) \in o(f(n))$, the same language is not recognizable in time $g$; it works for every such $g$. The "+1" is trivia for most reasonable functions (e.g., polynomials and exponential functions). Aug 7, 2019 at 16:17