Re:How to multiply polynomials in Θ(n log n) time
by pbsd on Monday September 07, 2015 @07:11PM
(#10183430)
The best complexity these days [1] is essentially n log n. More precisely, O( n log n 8^(log* n) ), where log* is the extremely slow-growing iterated logarithm. The original Schönhage-Strassen algorithm is O(n log n log log n).
[1] http://arxiv.org/abs/1407.3360