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)$. This simplified algorithm is referred to as the Fast Fourier Transform or FFT. A 1024-point FFT can be calculated with only about 10,000 operations.