FFT & NTT

Fast Convolution in O(n log n)

1:00

How the Fast Fourier Transform reduces polynomial multiplication from O(n²) to O(n log n) by evaluating at roots of unity, and how the Number Theoretic Transform gives the same speed with exact integer arithmetic.

By the end, you can

Explain why naive polynomial multiplication costs O(n²) and state the FFT improvement.
Describe the three-step FFT pipeline: forward FFT, pointwise multiply, inverse FFT.
State what the n-th roots of unity are and identify the key symmetry ω^(n/2) = −1.
Trace the even/odd divide-and-conquer split and write the butterfly combine equations.
Derive the O(n log n) complexity from the recurrence T(n) = 2T(n/2) + O(n).
Determine the minimum power-of-2 FFT size needed to multiply two given polynomials.
Explain how the inverse FFT differs from the forward FFT (conjugate root, divide by n).
Compare FFT and NTT: identify why floating-point FFT can fail on integers and how NTT fixes it.
Recognize problem domains where FFT/NTT convolution applies (big integers, string matching, DSP, counting).

Up next in String Algorithms, Advanced DP & Competitive Techniques