You may remember from high school what a polynomial is. If so, you may also remember how to multiply two of them. But what if I told you that the method you were taught is slow as F? In this post we will connect polynomials with the Fourier Transform and convolutions, and show you how to multiply polynomials with O(nlogn) complexity instead of O(n2), being the latter the method that’s taught in high school. Polynomials: A Quick Recap Let's do a quick recap on what polynomials are. Formally defin...