If I’d asked you how to implement DFT, what’d you do?

You’d suggest me to take the sum in each polynomials and do them concurrently, fastest right? Wrong. 

We can do the *sum* faster. Remember Merge Sort? So here is the same, we do the sums concurrently, but instead of summing up in O(N) , we sum in O(lgn)! 

That’s it it’s so easy. The rest is just explanation around the algorithms. Hope it will help.