Given all roots, how do I find the coefficients of a polynomial in time faster than O(n^2)?

Question

Given all the roots of a polynomial, I have to figure out an algorithm that generates the coefficients faster than O(n^2). I'm having trouble approaching this problem. I'm pretty sure I'm supposed to use the concept of a Fast Fourier Transform or Inverse Fourier Transform, but I don't know how to modify the input to not be the nth roots of unity. Can anyone point me in the right direction?

Answer 1

Here is an O(n * (log n)^2) solution:

1. The base case: for one root a, the answer is just x - a.

2. Let's assume that we have a list of more than one root. We can solve the problem recursively for the first and the second half of the list and then multiply the results using Fast Fourier Transform.

The time complexity is obtained from the equation T(n) = 2 * T(n / 2) + O(n log n), which is O(n * (log n)^2) according to the Master theorem.