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

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.

Solved by gpt-5.6-sol high.