Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 41D / a / 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, thenThus a length-$2N$ transform requires two length-$N$ transforms and $O(N)$ further multiplications. Its multiplication count satisfiesSince $N$ is a power of two, iteration through ${\log }_2(2N)$ levels gives $M(2N)=O(N\log N)$.