|
3 | added 1 characters in body | ||
|
Is there a conceptual way to understand where the Fast Fourier Transform is avoiding redundant computation and thus achieving $O(\log O(n\log n)$ instead of $O(n^2)$. Consider a standard example of the FFT to multiply two polynomials faster. Its not obvious to me conceptually why the FFT should yield a faster way to multiply two polynomials. |
||||
|
|
2 | added 180 characters in body | ||
|
Is there a conceptual way to understand where the Fast Fourier Transform is avoiding redundant computation and thus achieving $O(\log n)$ instead of $O(n^2)$. Consider a standard example of the FFT to multiply two polynomials faster. Its not obvious to me conceptually why the FFT should yield a faster way to multiply two polynomials. |
||||
|
|
1 |
|
||
Why is the Fast Fourier Transform efficient?Is there a conceptual way to understand where the Fast Fourier Transform is avoiding redundant computation and thus achieving $O(\log n)$ instead of $O(n^2)$.
|
||||
