= 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, so
$$
\boxed{M(2^p)=p\,2^{p-1}=\tfrac n2\log_2n}.
$$
If products by one are omitted, every block saves one product. There are $n-1$ blocks across all stages, giving $M_{\rm nonunit}(n)=\frac n2\log_2n-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.
Back to article page
