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

Counting every twiddle-factor product, including multiplication by one, the recurrence is $M(n)=2M(n/2)+n/2$, with $M(1)=0$. Each of the $p$ levels costs $n/2$ products, soIf products by one are omitted, every block saves one product. There are $n-1$ blocks across all stages, giving $M_{\mathrm{nonunit}}(n)=\frac{n}{2}{\log }_{2}n-n+1$. The conventional complexity in either convention is $O(n\log n)$; additional savings are possible by treating multiplication by $\pm i$ as component swaps and sign changes.