Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2 / 41E / b / 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 satisfiesso induction gives $T(M)\le CM{\log }_{2}M$ for powers of two. This proves the needed fast Fourier transform bound rather than assuming it.

Part (a) computes the length-$2N$ DFT of the reflected vector $y$ and then recoversForming $y$ uses no multiplications and the final recovery uses only $N$. Therefore the discrete cosine transform costs at most