MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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