the fast Fourier transform
/ FOOR-yay /
A polynomial of degree n-1 can be described in two equivalent ways: by its list of n coefficients, or by its values at n distinct points (n points determine a unique degree n-1 curve, just as 2 points determine a line). The Discrete Fourier Transform is the conversion from coefficients to values at a special set of evaluation points; the fast Fourier transform is a divide-and-conquer way to do that conversion in O(n log n) instead of the obvious O(n^2).
The naive way evaluates the polynomial at each of n points separately, costing O(n) per point and O(n^2) total. The FFT's trick is the choice of evaluation points: the n complex roots of unity (the n points equally spaced around the unit circle), which have beautiful symmetry. Split a polynomial P(x) into its even-indexed coefficients and odd-indexed coefficients, forming two half-size polynomials Peven and Podd with P(x) = Peven(x^2) + x * Podd(x^2). Because the roots of unity come in pairs r and -r whose squares coincide, evaluating P at all n roots reduces to evaluating Peven and Podd at only n/2 squared points, then combining each pair with a cheap multiply-and-add (a butterfly). That is T(n) = 2 T(n/2) + O(n) = O(n log n). Running the same machinery with the inverse roots converts values back to coefficients.
The FFT is one of the most consequential algorithms ever found — it transformed signal processing, audio and image compression, and large-number arithmetic, and it is routinely called the workhorse behind much of modern digital technology. For algorithm design, its headline use is multiplying polynomials and huge integers in O(n log n). The honest subtleties: the clean version assumes n is a power of two (pad with zeros otherwise), and because it computes with complex floating-point roots of unity it carries small rounding errors — for exact integer work one often uses a number-theoretic transform over a modular field instead.
To evaluate P at the 4th roots of unity {1, i, -1, -i}, note 1 and -1 square to 1, and i and -i square to -1. So Peven and Podd need evaluating at only {1, -1} — half as many points — and a butterfly recombines each pair.
Roots of unity in plus/minus pairs let one evaluation at squared points serve both, yielding the O(n log n) split.
The textbook FFT assumes n is a power of two and uses complex roots of unity, so it carries floating-point rounding error; exact integer work usually uses a number-theoretic transform instead.