That's the whole magic of FFT, it can be done in O(n*log(n)). And this is a practical algorithm, unlike the many fascinating algorithms for multiplying matrices. GMP will switch to FFT for multiplying very large numbers, for example, as numbers laid out in digits (whether binary or decimal) are polynomials if you look at them from the right angle. For processing audio and video it very quickly becomes economical to do the convolution in the frequency domain.

EDIT: never mind, I just figured out that you pointed a typo in the parent comment. Straightforward implementation is indeed O(n^2)