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?

Improve this question
$\endgroup$
1
  • 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

Reset to default
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$.

Improve this answer
$\endgroup$

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.