Comment by zahlman

We had O(n lg n) since 2019 already; now we (supposedly) know the limit is less than that (but of course at least linear).

> In 2019, Harvey and van der Hoeven came up with a galactic algorithm with complexity O ( n log ⁡ n ) {\displaystyle O(n\log n)}. This matches a guess by Schönhage and Strassen that this would be the optimal bound.

> In September 2026, OpenAI released a preprint claiming an algorithm with complexity O ( n ( log ⁡ n ) α ) {\displaystyle O(n(\log n)^{\alpha })} with α < 1 {\displaystyle \alpha <1}

https://en.wikipedia.org/wiki/Multiplication_algorithm

That said, it's interesting to contemplate that there is "space between" polynomial and exponential time complexities.