# Convolution without FFT

What is the best upper and lower bound known for convolution without FFT?

Is FFT proven to be essential for time complexity reduction? Is cancellation essential as well?

• It might be a good idea to clarify what you mean by FFT being essential for convolution. Jul 4 '13 at 21:19

Take a look at Toom-Cook multiplication and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon>0$.