This is why I keep coming back to HN. You read an interesting article, a little proud you understand half of it, read a question that already makes you feel like the stupidest person in the room, then read a clarifying answer by someone who probably got a Knuth reward check for correcting an errata in the art of computer programming.
Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/
Thanks, not often we see Knuth erratas. :)
<pedant>You never see "erratas", since "errata" is already the plural (of "erratum").</pedant>
The ensemble of errata of multiple books are erratas… probably.
Did he decide to include your better bound in future editions?
Yes. I believe proving the strict bound is one of the exercises now.
For FFT with floating-point numbers, another paper from Arnold Schönhage in 1982 [1] already gives the bound in Psi(n l) operations, where n is the number of coefficients, and l is the desired precision (typically 53 for double precision). Psi(m) is the time to multiply two integers with m digits, which is known since 2021 to be O(m log m) [2]. So the current bound is O(nl log(nl)).