fourier transform - Complexity of FFT derivation

I am confused regarding the complexity of the Fast Fourier Transform (FFT). The Discrete Fourier Transform is:

$$\qquad X\left [ k \right ]=\sum_{n=0}^{N-1}x[n]W_{N}^{kn}\quad \text{where}\quad W_{N}=e^{\frac{-j2\pi}{N}}\tag{1}$$

The first step in deriving the FFT is to express $(1)$ as the sum of even and odd inputs

$$\qquad X[k]=\sum_{n\ \rm even}x[n]W_{N}^{nk}\ +\ \sum_{n\ \rm odd}x[n]W_{N}^{nk}\tag{2}$$

And after many other derivations the final equation $(3)$ is obtained as

$$\qquad X[k]=\sum_{r=0}^{N/2-1}x[2r]W_{N/2}^{rk}\ +W_{N}^{k}\ \sum_{r=0}^{N/2-1}x[2r+1]W_{N/2}^{rk}\tag{3}$$

Equation $(3)$ consists of $2$ length $N/2$ FFTs, which is more computationally efficient than performing one big length $N$ FFT.

My question is: isn't equation $(2)$ also $2$ length $N/2$ FFTs? In other words, why all the bother about deriving equation $(3)$? Isn't equation $(2)$ already more computationally efficient than equation $(1)$? Or perhaps I'm missing something?

Any help is greatly appreciated.

Answer

Remember that the Cooley–Tukey algorithm seeks to calculate the original DFT recursively, partitioning each DFT into two of half the length in each recursion step. Therefore, it is necessary to express the DFT of length $N$ as two DFTs of length $N/2$.

The notation you used may be the cause of your confusion. Let me avoid using $W_N$. The second equation you wrote is then:

$$ X[k]= \sum_{m=0}^{\frac N 2 -1}x[2m]e^{-\frac{j2\pi}{N}(2m)k} + \sum_{m=0}^{\frac N 2 -1}x[2m+1]e^{-\frac{j2\pi}{N}(2m+1)k} \qquad(2) $$

The third one would be:

$$ X[k]= \sum_{m=0}^{\frac N 2 -1}x[2m]e^{-\frac{j2\pi}{N/2}mk} + e^{-\frac{j2\pi}{N}k} \sum_{m=0}^{\frac N 2 -1}x[2m+1]e^{-\frac{j2\pi}{N/2}mk} \qquad(3) $$

This way it's easier to see that in $(2)$ you do not have two DFTs. The second summation has the factor $(2m+1)$ in the exponential, which is different from the definition of DFT. If you factor it out, leading to that $\left(e^{-\frac{j2\pi}{N}k}\right)$ multiplying the second summation in $(3)$, then you have two DFTs: the one corresponding to the even-indexed part and the one corresponding to the odd-indexed one. That's why that additional step is made.