The FFT

• A brute force calculation of a length $N$ DFT requires a number of operations roughly proportional to $N^2$. Thus, a 1024-point DFT would require about a million multiplications and about a million additions.

• Luckily, the DFT algorithm can be simplified to a form in which the required number of calculations is proportional to $N \log(N).$ Now, our 1024-point DFT can be calculated with only about 10,000 operations!

• This simplified algorithm is referred to as the Fast Fourier Transform or FFT.