Polynomial to the power n algorithm

Question

Which is the best way to do polynomial powers? Is it by following the multinomial theorem (wikipedia) which takes O(?) or by FFT (fast Fourier transformation) and then inverse FFT with O((N*log(N))^2)?

Answer 1

FFT if you need to do it frequently, or on large polynomials. The naive multiplication algorithm is O(N^2), while FFT is O(N log(N)).

Here is a much better explanation with some neat applications: JeffE FFT