math - Computational complexity of the FFT in n dimensions

Question

What is the computational complexity of the n-dimensional FFT with m points along each dimension?

Answer 1

For a 1D FFT it's O(m log m).

For a 2D FFT you have to do m x 1D FFTs in each axis so that's O(2 m^2 log m) = O(m^2 log m).

It's too early in the morning here to get my head round n >= 3 but I'm guessing it's probably:

O(m^n log m)