Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 41D / c / Solution

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.