Editing Fast Fourier transform (section)

==Definition==
Let <math>x_0, \ldots, x_{n-1}</math> be [[complex number]]s. The [[discrete Fourier transform|DFT]] is defined by the formula

:<math> X_k = \sum_{m=0}^{n-1} x_m e^{-i2\pi k m/n} \qquad k = 0,\ldots,n-1, </math>

where <math>e^{i 2\pi/n}</math> is a [[Primitive root of unity|primitive]] {{mvar|n}}'th root of 1.

Evaluating this definition directly requires <math display="inline">O(n^2)</math> operations: there are {{mvar|n}} outputs {{mvar|X{{sub|k}}}}{{hairsp}}, and each output requires a sum of {{mvar|n}} terms. An FFT is any method to compute the same results in <math display="inline">O(n \log n)</math> operations. All known FFT algorithms require <math display="inline">O(n \log n)</math> operations, although there is no known proof that lower complexity is impossible.<ref name="Frigo_Johnson_2007"/>

To illustrate the savings of an FFT, consider the count of complex multiplications and additions for <math display="inline">n=4096</math> data points. Evaluating the DFT's sums directly involves <math display="inline">n^2</math> complex multiplications and <math display="inline">n(n-1)</math> complex additions, of which <math display="inline">O(n)</math> operations can be saved by eliminating trivial operations such as multiplications by 1, leaving about 30 million operations. In contrast, the radix-2 [[#Cooley–Tukey algorithm|Cooley–Tukey algorithm]], for {{mvar|n}} a power of 2, can compute the same result with only <math display="inline">(n/2)\log_2(n)</math> complex multiplications (again, ignoring simplifications of multiplications by 1 and similar) and <math display="inline">n\log_2(n)</math> complex additions, in total about 30,000 operations — a thousand times less than with direct evaluation. In practice, actual performance on modern computers is usually dominated by factors other than the speed of arithmetic operations and the analysis is a complicated subject (for example, see Frigo & [[Steven G. Johnson|Johnson]], 2005),<ref name="Frigo_Johnson_2005"/> but the overall improvement from <math display="inline">O(n^2)</math> to <math display="inline">O(n \log n)</math> remains.