# Non-Artifical Examples of Speedup / Non-Existence of Asymptotically optimal algorithm

Question: Are there any "real-world" examples of computable functions (such as integer multiplication/ matrix multiplication / etc.), where it is known that no asymptotically optimal algorithm exists?

Background: Over the past decades we have seen advancements in algorithms like matrix-multiplication that achieve lower and lower asymptotic computational complexity, such as Strassen's method or the Coppersmith-Winograd algorithm or the recent advance by Alman and Williams; yet, at the same time, besides Strassen none of these algorithms get used in practice since the coefficients get absurdly large, making them so-called Galactic algorithm's.

This raises the question: Are we in a situation where, there exists some lower bound like $$\mathcal O(n^{2})$$ (or $$\mathcal O(n^{2}\log n)$$, or $$\mathcal O(n^{c})$$ or whatever) that can never be achieved, but instead for any particular algorithm we find, there will be another one with a strictly lower asymptotic computational complexity.

It seems plausible that we could keep finding algorithms with complexity $$\mathcal O(n^{c+\epsilon})$$, yet at the same time the coefficients necessarily blow up as $$\epsilon\to 0$$. But what would this say about the usefulness of asymptotic complexity in practice? Does it mean that instead of trying to find fast algorithms for the general problem, one should rather spend time trying to find fast algorithms for the bounded problem $$n instead? Do we know for instance know what the fastest 8x8 (32x32 / 128x128 / ...) matrix multiplication algorithm is? For what $$n$$ do we know what the bilinear-complexity of the $$n\times n$$ matrix multiplication problem is? Doesn't this mean that, in practical terms, a more fruitful endeavor than finding asymptotically fast $$n\times n$$ matrix multiplication algorithms, would be to find fast multiplication algorithms for each $$n$$ individually, and then use a lookup table? To what degree is this even possible (combinatorial explosion) ??

To clarify what we mean by “optimal”: given any universal code, let $$p(n)$$ be the implied probability of the code word for $$n$$ ($$2^{-k}$$ for a word of length $$k$$). Then there exists a “better” code whose implied probabilities satisfy $$\frac{q(n)}{p(n)} \to \infty$$.
For example, one universal code is Elias gamma coding, which represents a number $$n$$ by $$\lfloor\log_2 n\rfloor$$ zero bits followed by the binary representation of $$n$$. Its implied probabilities are $$2^{-2\lfloor\log_2 n\rfloor - 1} = Θ\bigl(\frac{1}{n^2}\bigr)$$. A better universal code is Elias delta coding, whose implied probabilities are $$Θ\bigl(\frac{1}{n \log^2 n}\bigr)$$.
If there were some function that can be computed in time $$Θ\bigl(\frac{1}{p(n)}\bigr)$$ for any universal code, it would provide an answer to your question. It’s hard to imagine exactly what such a function might look like, but I don’t see any reason to rule it out.