mathcomplexity-theoryfft

Computational complexity of the FFT in n dimensions

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

Solution

  • 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)