Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 39A / 1 / Solution

Separate even and odd indices, using ${\omega }_{2m}^2={\omega }_m$. ThenThe second identity uses ${\omega }_{2m}^m=-1$. Each FFT butterfly uses one shared twiddle-factor product and two additions, so assembly costs $m$ multiplications and $2m$ additions.