The computational complexity of n-dimensional Fast Fourier Transform was discussed here and (as the former's duplicate) here.
The computational complexity of a 1-dimensional Discrete Fourier Transform is O(N^2), N is the data set size.
Could you please tell us what is the computational complexity of the n-dimensional Discrete Fourier Transform consisting {N1, N2 ... Nn} points along each dimension?
The FFT itself is also a DFT (with some constraints). Will assume that you mean the naive summation method.
Re-writing the 1D DFT in integral form (the continuous version):
A particular value of f-tilde is equivalent to a single element in your DFT array. When the integral is discretized (i.e. converted a finite sum), there are N terms in the sum. This gives O(N) for each element and hence O(N^2) overall.
In case you were wondering, writing in this form allows for more compact notation for a general n-D DFT:
When this is discretized, we can see that for each element there are n sums, each over one of the dimensions and of length N. There are N ^ n values in the input "array", so the complexity is:
