Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 40E / b / Solution

The radix-two Fast Fourier transform recursively applies part (a) until it reaches one-point transforms, then combines adjacent even and odd transforms in butterfly operations. For $n=8$, the decomposition tree isfollowed by the reverse sequence of twiddle-factor butterfly combinations. This is the usual three-stage FFT network.