= Solution
Put $\omega_{2N}=e^{-\pi i/N}$ and split the transform into its even and odd input samples. If $E_k$ and $O_k$ are the two length-$N$ transforms, then
$$
Y_k=E_k+\omega_{2N}^kO_k,
\qquad
Y_{k+N}=E_k-\omega_{2N}^kO_k,
\qquad 0\leq k<N.
$$
Thus a length-$2N$ transform requires two length-$N$ transforms and $O(N)$ further multiplications. Its multiplication count satisfies
$$
M(2N)\leq2M(N)+CN.
$$
Since $N$ is a power of two, iteration through $\log_2(2N)$ levels gives $M(2N)=O(N\log N)$.
Back to article page
