Is there a conceptual way to understand where the Fast Fourier Transform is avoiding redundant computation and thus achieving $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.



Why is the Fast Fourier Transform efficient?
Conceptually the FFT takes advantage of a shortcut similar to the distributive law for multiplication. To compute $$(x\_1 + x\_2)(x\_3 + x\_4)$$ on could either add first (twice) and then multiply (once), or one could expand $$sx\_1x\_3 + x\_1x\_4 + x\_2x\_3 + x\_2x\_4$$ and multiply (four times) and then add (three times). This idea has been spelled out in the paper [The Generalized Distributive Law](http://www.mceliece.caltech.edu/publications/GDL.ps).


