= Even--odd fast Fourier transform recursion
For even length $N=2m$, split the input of a <discrete Fourier transform> into its even and odd samples, $x_{2r}$ and $x_{2r+1}$. Let $E_k,O_k$ be their length-$m$ <discrete Fourier transforms>, with negative-exponent convention. Splitting the original <sum> by the parity of its index gives, for $0\leq k<m$,
$$
Y_k=E_k+\omega_N^kO_k,\qquad
Y_{k+m}=E_k-\omega_N^kO_k,\qquad
\omega_N=e^{-2\pi i/N}.
$$
The sign change follows from $\omega_N^m=-1$. Thus the same two short transforms supply both halves of the result through an <FFT butterfly>. For $N=2^p$, recursive splitting reaches length one after $p$ levels. Each level needs $O(N)$ arithmetic operations, so the <time complexity> is $O(N\log N)$. For example, a length-four transform uses the two length-two transforms of $(x_0,x_2)$ and $(x_1,x_3)$, then twiddle factors $1$ and $-i$.<Notes on the FFT by C. Sidney Burrus>[Cooley-Tukey algorithm and decimation-in-time factorization]{ref}
Back to article page