Fast Fourier Transform
- is an algorithm that computes the discrete Fourier transform (DFT) of a sequence FAST, or its inverse (IDFT)
- direct computation of the DFT is computationally expensive, with a complexity of π(π2)
- FFTs, like the Cooley-Tukey algorithm, reduce this complexity to π(π πππ π) by exploiting the symmetries and redundancies in the DFT calculation