FFT — Fast Fourier Transform (Cooley–Tukey)
Key insight: DFT of N points = 2 × DFT of N/2 points + N/2 multiplications
X[k] = E[k] + WkN · O[k]
X[k+N/2] = E[k] − WkN · O[k]
(butterfly operation)
Butterfly diagram — all stages (N=8)
Complexity — operations vs N