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.