computational complexity of convolution

Question

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?

Answer 1

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.