= Solution
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.
Back to article page
