What is the computational complexity of an n-dimensional FFT with m points along each dimension?
For 1D FFT this O(m log m).
O(m log m)
For 2D FFT, you need to make mx 1D FFT on each axis to O(2 m^2 log m)= O(m^2 log m).
O(2 m^2 log m)
O(m^2 log m)
It's too early in the morning here to get a head n >= 3, but I guess this is possible:
n >= 3
O(m^n log m)