An FFT algorithm computes the discrete Fourier transform (DFT) of a sequence or its inverse (IFFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. A FFT computes such transformations rapidly by factoring the DFT matrix into a product of sparse matrices. As a result, a FFT reduces the complexity of computing the DFT from $O(n^2)$ if one applies the definition of the DFT to $O(n\log n)$ where $n$ is the data size.