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?

  • 1
    $\begingroup$ It might be a good idea to clarify what you mean by FFT being essential for convolution. $\endgroup$
    – Kaveh
    Commented Jul 4, 2013 at 21:19

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.