You can do this in O(n^2)
very easily if you incrementally build your polynomial. Let's define:
p_k(x) = (x-x_1)*...*(x-x_k)
That is p_k(x)
is the multiplication of the first k
(x-x_i)
of p(x)
. We have:
p_1(x) = x-x_1
In other words the array of coefficients (a
) would be (indices start from 0 and from left):
-x_1 1
Now assume we have the array of coefficients for p_k(x)
:
a_0 a_1 a_2 ... a_k
(side note: a_k
is 1). Now we want to calculate p_k+1(x)
, which is (note that k+1
is the index, and there is no summation by 1):
p_k+1(x) = p_k(x)*(x-x_k+1)
=> p_k+1(x) = x*p_k(x) - x_k+1*p_k(x)
Translating this to the array of coefficients, it means that the new coefficients are the previous ones shifted to the right (x*p_k(x)
) minus the k+1
th root multiplied by the same coefficients (x_k+1*p_k(x)
):
0 a_0 a_1 a_2 ... a_k-1 a_k
- x_k+1 * (a_0 a_1 a_2 a_3 ... a_k)
-----------------------------------------
-x_k+1*a_0 (a_0-x_k+1*a_1) (a_1-x_k+1*a_2) (a_2-x_k+1*a_3) ... (a_k-x_k+1*a_k-1) a_k
(side note: and that is how a_k
stays 1) There is your algorithm. Start from p_1(x)
(or even p_0(x) = 1
) and incrementally build the array of coefficients by the above formula for each root of the polynomial.