Let $C_j(\xi)$ denote the $j$th discrete cosine coefficient of $\xi_n=(-1)^nx_n$. For $0\leq k<N$,
$$
\begin{aligned}
C_{N-1-k}(\xi)
&=\sum_{n=0}^{N-1}(-1)^nx_n
\cos\left(\pi\left(n+\frac12\right)
-\frac{\pi}{N}\left(n+\frac12\right)(k+1)\right)\\
&=\sum_{n=0}^{N-1}x_n
\sin\left(\frac{\pi}{N}\left(n+\frac12\right)(k+1)\right)
=\widetilde Z_k.
\end{aligned}
$$
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.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/41d/d/solution