computational complexity of convolution

complexity-theory, convolution, fft

Solution

As for two- and three-dimensional convolution and Fast Fourier Transform the complexity is following:

                            2D                     3D

Convolution               O(n^4)                  O(n^6)

FFT                   O(n^2 log^2 n)           O(n^3 log^3 n)

Reference: Slides on Digital Image Processing, slide no. 34.

Problem

I read that the computational complexity of the general convolution algorithm is `O(n^2)`, while by means of the FFT is `O(n log n)`. What about convolution in 2-D and 3-D? Any reference?

Original source