This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem.<p>In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you&#x27;ll get the wrong answer. I think it ends up being an O(n log^2 n) algorithm. Still pretty good; worth knowing about for sure. The constant factor on the precision might be bad enough that you can trigger the problem for reasonable inputs if you&#x27;re using floats (e.g. a million coefficients, instead of an octillion coefficients).<p>On the other hand, many algorithms and data structures have hidden logarithmic factors (e.g. hash tables, sorting) that we ignore [1]. YMMV.<p>1: <a href="http:&#x2F;&#x2F;blog.computationalcomplexity.org&#x2F;2009&#x2F;05&#x2F;shaving-logs-with-unit-cost.html" rel="nofollow">http:&#x2F;&#x2F;blog.computationalcomplexity.org&#x2F;2009&#x2F;05&#x2F;shaving-logs...</a>