Mixed-radix and Bluestein reductions compute every finite DFT in O(N log N) arithmetic

We prove correctness by strong induction on $N$, justified by [F8]. At $N=1$, step 1 of the formal model returns $x_0$, the one-term unnormalised DFT. If $N$ is a power of two, its radix-two branch calls the exact unitary transform and scales by $\sqrt{N}$; [F5] identifies that result with the unnormalised DFT.

For the induction step, assume the formal model returns the unnormalised DFT for every positive length smaller than $N$.

For a power-of-two size $M\ge 2$, [F3] gives $O(M{\log }_{2}M)$; the output normalization uses one square root and $O(M)$ component scalings, which preserve this order. In a Bluestein branch, the least power of two $M\ge 2N-1$ satisfies $M<4N$, and three radix-two transforms plus $O(M)$ pointwise products/scalings cost $O(M{\log }_{2}M)$. Since ${\log }_{2}M\le {\log }_2(4N)=2+{\log }_{2}N\le 3{\log }_{2}N$ for $N\ge 2$, this is $O(N{\log }_{2}N)$ for a prime input $N$.

If $N$ is composite and not a power of two, the least-divisor branch splits $N=rs$ with $r,s<N$. The hypothesis in step 1.2 makes the recursive unnormalised length-$s$ and length-$r$ transforms exact. By [F6], the length-$s$ output on each strided vector is $\sqrt{s}{\mathcal{F}}_s{x}^{(u)}$, and a length-$r$ unnormalised transform is $\sqrt{r}$ times the unitary length-$r$ DFT. The fixed strided inputs, exact phase factors, and output indexing are those in [F2], so the algorithm combines the recursive outputs as $X_{k_2+s{k}_1}={\sum }_{u=0}^{r-1}{U}_u(k_2)e^{-2\pi iu{k}_2\mathrm{/}N}{e}^{-2\pi iu{k}_1\mathrm{/}r}$. This is the unnormalised mixed-radix formula; hence every output is exact.

If $N$ is prime, [F2] gives ${\mathcal{F}}_{N}x=N^{-1\mathrm{/}2}\gamma \odot c$ for the exact cyclic convolution $c$ in the Bluestein branch. The formal model computes $c$ exactly by [F4]. Multiplying the unitary output identity by $\sqrt{N}$ gives $X_N=\gamma \odot c$, which is exactly the unnormalised output of the branch. The base, power-of-two, composite and prime cases exhaust all positive $N$.

At a composite non-power-of-two node $N=rs$, the algorithm's actual call schedule invokes $r$ transforms of size $s$ and $s$ transforms of size $r$, plus at most $CN$ arithmetic operations for a fixed $C$. Thus $T(N)\le rT(s)+sT(r)+CN$, so the normalized count $S(N):=T(N)\mathrm{/}N$ satisfies $S(N)\le S(r)+S(s)+C$. For the bound, build a separate binary comparison tree by expanding this normalized recurrence at each composite non-power-of-two size; stop at prime or power-of-two sizes. This tree is finite because every child size is smaller than its parent, and its terminal sizes $n_1,\dots ,n_L$ multiply to $N$ because each split replaces $n$ by factors $r,s$ with $n=rs$. Every terminal size is at least $2$, so $2^L\le N$ and [F7] gives $L\le {\log }_{2}N$. A full binary tree with $L$ leaves has $L-1$ internal nodes: a leaf has zero internal nodes, while a root with subtrees having $L_1,L_2$ leaves has $1+(L_1-1)+(L_2-1)=L_1+L_2-1$ internal nodes, by induction on height [F8]. The product law in [F7] gives ${\sum }_{i=1}^L{\log }_2{n}_i={\log }_{2}N$. By steps 1.1 and 1.3, each terminal size $n_i$, whether prime or a power of two, contributes $O({\log }_2{n}_i)$ to $S$, with one uniform constant. Summing the terminal contributions and the at most $C$ contribution at each internal node yields $S(N)=O({\log }_{2}N)$ and hence $T(N)=O(N{\log }_{2}N)$. The comparison tree bounds the normalized recurrence; it is not the algorithm's actual call tree.