title: Computational complexity of n-dimensional Discrete Fourier Transform?
body: <p>The <a href="https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm">computational complexity</a> of n-dimensional Fast Fourier Transform was discussed <a href="https://stackoverflow.com/questions/6514861/computational-complexity-of-the-fft-in-n-dimensions">here</a> and (as the former's duplicate) <a href="https://stackoverflow.com/questions/12249275/computational-complexity-of-an-n-dimensional-fast-fourier-transform">here</a>.</p>
  
  <p>The computational complexity of a 1-dimensional <a href="https://en.wikipedia.org/wiki/Discrete_Fourier_transform" rel="nofollow noreferrer">Discrete Fourier Transform</a> is <a href="https://en.wikipedia.org/wiki/Fast_Fourier_transform" rel="nofollow noreferrer"><code>O(N^2)</code></a>, <code>N</code> is the data set size.</p>
  
  <p>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?</p>