Fast Fourier transform

A fast Fourier transform (FFT) algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse. Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from ${\displaystyle O(n^{2})}$, which arises if one simply applies the definition of DFT, to ${\displaystyle O(n\log n)}$, where ${\displaystyle n}$ is the data size.

...
Wikipedia