4

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

Charles
  • 50,943
  • 13
  • 104
  • 142
Dan
  • 12,157
  • 12
  • 50
  • 84
  • possible duplicate of [Computational complexity of an n-dimensional Fast Fourier Transform?](http://stackoverflow.com/questions/12249275/computational-complexity-of-an-n-dimensional-fast-fourier-transform) –  Apr 26 '15 at 20:39

1 Answers1

7

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)
Paul R
  • 208,748
  • 37
  • 389
  • 560
  • 4
    This is right, but it is really O(2^n m^n log m) - just pointing out that the coefficient grows exponentially with n as well. – GeorgeWilson Jun 04 '14 at 23:12