Fast Fourier Transform

An algorithmic family that computes the discrete Fourier transform (DFT) of a sequence efficiently by exploiting symmetries, periodicities, and recursive factorization of the DFT matrix to reduce arithmetic complexity from O(N^2) to O(N log N) in common cases.