FFT vs Naive Convolution: A 1000× Speedup from Math

Same mathematical result. Radically different cost. The FFT exploits roots of unity to reduce O(n²) multiplications to O(n log n).

n = 10,000
Naive O(n²)
—
FFT O(n log₂ n)
—
Speedup
—

Op Count (log scale)

Naive n²
FFT n·log n
Bar height proportional to log₁₀(ops). Visual difference dramatic at large n.