Let x0, ...., xn-1 be complex numbers. We will assume for simplicity that n is a power of two; since the number of sample points n can usually be chosen freely by the application, this is no important restriction. Evaluating the formulas
![[Home]](wikipedia.png)
n-1
fj = 1/n ∑ xk e-2πijk/n j = 0,...,n-1
k=0
directly would take O(n2) arithmetical operations (see Big O). The basic idea of the Fast Fourier Transform is to reduce this runtime to O(n log n) by using a recursive approach: first compute the Fourier transforms of the even indexed numbers x0, x2,....,xn-2, and of the odd indexed numbers x1, x3,....,xn-1, and then combine those two results to produce the Fourier transform of the whole sequence.
We write n' = n/2 and denote the discrete Fourier transform of the even indexed numbers x'0 = x0, x'1 = x2,....,x'n'-1 = xn-2 by f'0,...,f'n'-1, and the transform of the odd indexed numbers x''0 = x1,x''1 = x3,...,x''n'-1 = xn-1 by f''0, ..., f''n'-1. Then it follows:
n/2-1 n/2-1
fj = 1/n ∑ x2k e-2πij(2k)/n + 1/n ∑ x2k+1 e-2πij(2k+1)/n
k=0 k=0
n'-1 n'-1
= 1/n ∑ x'k e-2πijk/n' + 1/n e-2πij/n ∑ x''k e-2πijk/n'
k=0 k=0
/ 1/2 f'j + 1/2 e-2πij/n f''j if j<n'
= {
\ 1/2 f'j-n' + 1/2 e-2πij/n f''j-n' if j≥n'
This trick was already known to Gauss, who used it in orbital computations in astronomy. It became popular in 1965 after Cooley-Tukey published a paper describing how to arrange the numbers occurring in the algorithm conveniently in an array.