(a) Let $\mathbf{x} \in \mathbb{R}^{N}$ and define $\mathbf{y} \in \mathbb{R}^{2 N}$ by

$$y_{n}= \begin{cases}x_{n}, & 0 \leqslant n \leqslant N-1 \\ x_{2 N-n-1}, & N \leqslant n \leqslant 2 N-1\end{cases}$$

Let $\mathbf{Y} \in \mathbb{C}^{2 N}$ be defined as the discrete Fourier transform (DFT) of $\mathbf{y}$, i.e.

$$Y_{k}=\sum_{n=0}^{2 N-1} y_{n} \omega_{2 N}^{n k}, \quad \omega_{2 N}=\exp (-\pi i / N), \quad 0 \leqslant k \leqslant 2 N-1$$

Show that

$$Y_{k}=2 \omega_{2 N}^{-k / 2} \sum_{n=0}^{N-1} x_{n} \cos \left[\frac{\pi}{N}\left(n+\frac{1}{2}\right) k\right], \quad 0 \leqslant k \leqslant 2 N-1$$

(b) Define the discrete cosine transform $(\mathrm{DCT}) \mathcal{C}_{N}: \mathbb{R}^{N} \rightarrow \mathbb{R}^{N}$ by

$$\mathbf{z}=\mathcal{C}_{N} \mathbf{x}, \text { where } z_{k}=\sum_{n=0}^{N-1} x_{n} \cos \left[\frac{\pi}{N}\left(n+\frac{1}{2}\right) k\right], \quad k=0, \ldots, N-1$$

For $N=2^{p}$ with $p \in \mathbb{N}$, show that, similar to the Fast Fourier Transform (FFT), there exists an algorithm that computes the DCT of a vector of length $N$, where the number of multiplications required is bounded by $C N \log N$, where $C$ is some constant independent of $N$.

[You may not assume that the FFT algorithm requires $\mathcal{O}(N \log N)$ multiplications to compute the DFT of a vector of length $N$. If you use this, you must prove it.]