Solution
= Solution
If $C(n)$ counts complex multiplications and a twiddle product is reused in the two butterfly outputs, then
$$
C(n)=2C(n/2)+\frac n2,
\qquad C(1)=0.
$$
For $n=2^k$, solving the recurrence gives
$$
\boxed{C(n)=\frac n2\log_2n=2^{k-1}k}.
$$