[proofplan]
We count the total number of complex multiplications in the FFT by analysing its recursive structure. The algorithm has $p = \log_2 n$ stages (since $n = 2^p$). At each stage $s$ (for $s = 1, \ldots, p$), the algorithm reconstructs $2^{p-s}$ length-$2^s$ DFTs from pairs of length-$2^{s-1}$ DFTs using the [DFT Splitting Identity](/theorems/1371). Each reconstruction requires $2^{s-1}$ twiddle-factor multiplications, giving $2^{p-s} \cdot 2^{s-1} = 2^{p-1}$ multiplications per stage. Summing over all $p$ stages yields $p \cdot 2^{p-1} = \frac{1}{2} n \log_2 n$.
[/proofplan]
[step:Describe the recursive structure of the FFT algorithm]
The FFT computes $\mathcal{F}_n y$ for $n = 2^p$ by recursively applying the [DFT Splitting Identity](/theorems/1371). At each level of recursion, a length-$2^s$ DFT is expressed in terms of two length-$2^{s-1}$ DFTs (one on the even-indexed subsequence and one on the odd-indexed subsequence) plus $2^{s-1}$ multiplications by twiddle factors $\omega_{2^s}^\ell$ for $\ell = 0, \ldots, 2^{s-1} - 1$.
The recursion begins with the $2^p$ individual entries of $y$ (length-$1$ DFTs, which require no computation) and proceeds through $p$ stages:
- **Stage $s = 1$**: Combine pairs of length-$1$ DFTs into $2^{p-1}$ length-$2$ DFTs.
- **Stage $s = 2$**: Combine pairs of length-$2$ DFTs into $2^{p-2}$ length-$4$ DFTs.
- $\vdots$
- **Stage $s = p$**: Combine $2$ length-$2^{p-1}$ DFTs into $1$ length-$2^p = n$ DFT.
[/step]
[step:Count the multiplications at each stage]
At stage $s$ (for $s = 1, \ldots, p$), the algorithm must compute $2^{p-s}$ parent DFTs, each of length $2^s$. By the [DFT Splitting Identity](/theorems/1371), reconstructing one length-$2^s$ DFT from its two length-$2^{s-1}$ children requires computing the products $\omega_{2^s}^\ell \cdot (\mathcal{F}_{2^{s-1}} z^{(\mathrm{o})})_\ell$ for $\ell = 0, \ldots, 2^{s-1} - 1$. This contributes $2^{s-1}$ complex multiplications per parent DFT.
The total number of complex multiplications at stage $s$ is therefore
\begin{align*}
(\text{number of parent DFTs at stage } s) \times (\text{multiplications per parent}) = 2^{p-s} \cdot 2^{s-1} = 2^{p-1}.
\end{align*}
This count is independent of $s$: every stage performs exactly $2^{p-1} = \frac{n}{2}$ complex multiplications.
[guided]
Why is the multiplication count the same at every stage? At stage $s$, there are fewer parent DFTs ($2^{p-s}$ decreases with $s$) but each one is larger and requires more twiddle-factor multiplications ($2^{s-1}$ increases with $s$). These two effects cancel exactly: the product $2^{p-s} \cdot 2^{s-1} = 2^{p-1}$ is constant.
To be precise about what counts as a "multiplication": at each butterfly, the splitting identity gives
\begin{align*}
(\mathcal{F}_{2^s}z)_\ell &= (\mathcal{F}_{2^{s-1}} z^{(\mathrm{e})})_\ell + \omega_{2^s}^\ell \, (\mathcal{F}_{2^{s-1}} z^{(\mathrm{o})})_\ell, \\
(\mathcal{F}_{2^s}z)_{\ell+2^{s-1}} &= (\mathcal{F}_{2^{s-1}} z^{(\mathrm{e})})_\ell - \omega_{2^s}^\ell \, (\mathcal{F}_{2^{s-1}} z^{(\mathrm{o})})_\ell.
\end{align*}
The product $\omega_{2^s}^\ell \cdot (\mathcal{F}_{2^{s-1}} z^{(\mathrm{o})})_\ell$ is computed once and used in both the addition and subtraction. So each value of $\ell$ contributes exactly one complex multiplication (the twiddle factor), and the additions/subtractions are not counted as multiplications (they are cheaper operations). There are $2^{s-1}$ values of $\ell$ per parent, giving $2^{s-1}$ multiplications per parent.
[/guided]
[/step]
[step:Sum over all stages to obtain $\frac{1}{2} n \log_2 n$]
Summing the multiplication count over all $p$ stages:
\begin{align*}
\text{Total multiplications} = \sum_{s=1}^{p} 2^{p-1} = p \cdot 2^{p-1}.
\end{align*}
Since $n = 2^p$, we have $p = \log_2 n$ and $2^{p-1} = \frac{n}{2}$. Therefore
\begin{align*}
\text{Total multiplications} = \frac{n}{2} \cdot \log_2 n = \frac{1}{2} n \log_2 n.
\end{align*}
Each complex multiplication requires $O(1)$ real arithmetic operations, and the additions at each butterfly also contribute $O(n)$ operations per stage (hence $O(n \log n)$ in total). Since $\frac{1}{2} n \log_2 n \in O(n \log n)$, the overall time complexity of the FFT algorithm is $O(n \log n)$.
[/step]
