On parallel calculations for discrete Fourier transformation

The problem of asymptotic estimate of the time complexity of numerical Fourier transformation is considered. The conditions are found under which a well known estimation may be achieved. It is shown that a contradiction between FFT and DFT under these conditions is not reasonable.