Why do we need FFT

Computing an N-point DFT directly needs N² complex multiplications and N(N−1) complex additions. For large N (for example 1024 points: about one million multiplications) this is too slow for real-time processing.

The FFT exploits the symmetry and periodicity of the twiddle factor W_N^(kn) to split the DFT into smaller DFTs. It needs only (N/2)log₂N complex multiplications and N log₂N additions. For N = 1024 that is 5120 against 1,048,576 multiplications, about 200 times faster. This makes real-time spectrum analysis, fast convolution and filtering, and communications systems practical.