Exercise 4.3.7

We can follow the same pattern for 1D FFT as in IV.1, e.g. equation (11), where we decompose the Fourier matrix ${\mathrm{\Omega }}_N$ into ${\mathrm{\Omega }}_{\frac{N}{2}}$, and recurse until there’s only 1 element in the matrix.

In 2D, it now involves Kronecker product which is more complicated. Since in 2D DFT, we apply 1D DFT twice on rows and columns, so we probably can count them independently here, so

For an $n$ by $n$ image, since we have reductions from both dimensions, the final count for size $n=2^l$ is reduced from $n^2{n}^2=n^4$ to

Each level $l$ will need $\frac{1}{4}{n}^2$ calculations.