3
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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