Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 41D (Numerical Analysis)

Put ${\omega }_{2N}=e^{-\pi i/N}$ and split the transform into its even and odd input samples. If $E_k$ and $O_k$ are the two length-$N$ transforms, thenThus a length-$2N$ transform requires two length-$N$ transforms and $O(N)$ further multiplications. Its multiplication count satisfiesSince $N$ is a power of two, iteration through ${\log }_2(2N)$ levels gives $M(2N)=O(N\log N)$.

Pair the two entries of the even-reflected sequence that contain $x_n$. For every $k$,Consequentlyfor $0\le k<2N$, as required.

Constructing the reflected vector $y$ costs $O(N)$ assignments. Part (a) computes all of its Fourier coefficients in $O(N\log N)$ multiplications, and part (b) recovers the required coefficients $Z_0,\dots ,Z_{N-1}$ with one phase multiplication per coefficient. Hence the whole discrete cosine transform costs $O(N\log N)$ multiplications.

Let $C_j(\xi )$ denote the $j$th discrete cosine coefficient of ${\xi }_n=(-1{)}^n{x}_n$. For $0\le k<N$,The identity uses $\cos (\pi (n+1/2)-u)=(-1{)}^n\sin u$. Sign-modulating the input and reversing the $N$ cosine-transform outputs each cost $O(N)$ operations, so part (c) gives the sine transform in $O(N\log N)$ multiplications.