= Solution
For a length-$M$ DFT with $M$ even, split the input into its even and odd entries. Two length-$M/2$ DFTs determine the result, followed by at most $M$ multiplications by twiddle factors. Hence the multiplication count satisfies
$$
T(M)\leq2T(M/2)+M,
$$
so induction gives $T(M)\leq CM\log_2M$ for powers of two. This proves the needed <Cooley--Tukey fast Fourier transform>[fast Fourier transform] bound rather than assuming it.
Part (a) computes the length-$2N$ DFT of the reflected vector $y$ and then recovers
$$
z_k=\frac12\omega_{2N}^{k/2}Y_k,\qquad0\leq k<N.
$$
Forming $y$ uses no multiplications and the final recovery uses only $N$. Therefore the <discrete cosine transform> costs at most
$$
\boxed{C(2N)\log(2N)+N=O(N\log N).}
$$
Back to article page
