What is the intuition of FFT for polynomial? Multiplications on two ($N-1$)-degree polynomial is naively done in $O(N^2)$. Using FFT, we can reduce the complexity to $O(N\log N)$. As for addition, w/ or w/o FFT, the complexity is $O(N)$ in both cases.
I know this fact. But I do not understand the intuition.
Why does this hold?