As the author mentions, convolutions for signal processing and convolutions for probability are essentially equivalent things in two different contexts. It is interesting that the same concept is behind the multiplication of polynomials. In the discrete case we have the parallel of the vectors representing ... the (discretized) probability density the (discrete) signal intensity the coefficients of the polynomial ...…
Discrete convolution is O(n^2).
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)