Fast Fourier Transform (FFT)
An efficient algorithm that computes the Discrete Fourier Transform (DFT) of a sequence in O(N log N) operations instead of O(N²).
Governing formula
Cooley-Tukey Divide-and-Conquer: O(N log N) vs O(N²)
SI unit
Computational FFT Algorithm
In depth
Developed by James Cooley and John Tukey in 1965. Exploits periodic symmetries in complex roots of unity to recursively split N-point DFTs into smaller sub-transforms, drastically reducing computation time.
Examples in the real world
Real-time audio signal spectral analysis, image processing, and fast PDE solvers.