What is Discrete and fast Fourier transforms?

The discrete Fourier transform of $x_0, \dots, x_{N-1}$ is $X_k = \sum_{j=0}^{N-1}x_je^{-2\pi\mathrm ijk/N}$, $k = 0, \dots, N - 1$. A fast Fourier transform computes it in $O(N\log N)$ operations instead of $O(N^2)$ by splitting it recursively into transforms of half the length (Cooley and Tukey, 1965).