Fast Fourier Transform (FFT)

We can rewrite the DFT Formula: $X(k)={\sum }_{n=0}^{N-1}x(n)e^{-j2\pi k(n/N)}k=0,1,..N-1$ as $X(k)={\sum }_{n=0}^{N-1}x(n)W_N^{kn},W_N=e^{-j2\pi /N}$

Now the problem for DFT is that both k and n are in the range of N, which means we need $N^2$ multiplications. So how do we reduce this?

It turns out that splitting it in two means that it takes $2(N/2{)}^2=\frac{N^2}{2}$, which is half of what we started with. Naturally, the next conclusion is to keep subdividing. The formal “recipe” for calculation is

$$X_i(k)=X_{ie}(k)+W_L^k{X}_{io}(k)$$