| Here's how the (boring, radix-2) fast Fourier transform (FFT) works:
"Recall" that the discrete Fourier transform (DFT; what we're trying to calculate quickly) is defined by
F(j) = Σk=0N-1 f(k) wk*j,
where f is a (periodic) function defined on N points, F is its Fourier transform, and w=exp(i/(2*pi*N)) is a primitive N'th root of 1. Now suppose that N>1 is a power of 2. Then we can separate out the sum above by even and odd k, to get
F(j) = Σk=0N/2-1 (f(2k) + wj f(2k+1))*w^2kj
which is almost the DFT of the function
g(k) = f(2k) + wj f(2k+1)
g(k+N/2) = f(2k) - wj f(2k+1)
and is not quite N/2-periodic. But if we calculate the Fourier transforms of f at even and odd points:
F0(j) = Σk=0N/2-1 f(2k) w2kj
F1(j) = Σk=0N/2-1 f(2k+1) w2kj
then
F(j) = F0(j) + wj F1(j)
So to calculate one Fourier transform of N points, we must calculate 2 Fourier transforms of N/2 points. This yields time complexity of O(n log n), much better than the naïve algorithm's running time of O(n^2).
| 
