# Calculating a polynomial's coefficients from its roots

Let $$P$$ be a monic polynomial polynomial given by its roots: $$P(X) = (X-x_1)\times...\times(X-x_n)$$

What is the minimum asymptotic complexity to compute its expansion of the form: $$a_nX^n+...+a_0$$

What I have found so far are Vieta's formulas which give an expression of each $$a_k$$ as a sum over $$1\leq i_1 < ... < i_{n-k} \leq n$$. This would suggest the complexity of computing the $$k$$th coefficient is something like $${n-1 \choose n-k-1}={n-1 \choose k}=O(n^k)$$, thus making the total complexity bonkers (I guess something like $$O(n^n)$$).

Yet my teacher's presentation suggests it is a $$O(n^2)$$, which doesn't match my calculation at all.

For every integer $$i$$, $$0\le i\le n$$, let $$P_i(X) = (X-x_1)(X-x_2)\cdots(X-x_i)=a_{i,i}X^i+a_{i,i-1}X^{i-1}+\cdots+...+a_{i,0}$$ for some $$a_{i,k}$$, $$0\le k\le i$$. In particular, $$a_{i,i}=1$$. Expanding $$P$$ on both sides of the following equation and comparing the coefficients, $$P_{i+1}(X) = P_i(X)(X-x_{i+1})$$ we see that for $$1\le k\le i\lt n$$, $$a_{i+1,k}=-a_{i,k}x_{i+1}+a_{i,k-1}$$ and $$a_{i+1,0} = -a_{i,0}x_{i+1}$$ So for fixed $$i$$, we can compute all coefficients of $$P_{i+1}(X)$$ from the coefficients of $$P_i(X)$$ with $$O(i)$$ steps. Now you should be able to see that your professor's suggestion on the minimum asymptotic complexity makes a lot of sense.
• Thanks! I actually figured out another way of seeing whilst reading your answer: one can calculate $\sigma_{k+1}$ in $n$ operations from $\sigma_k$ (multiply by each root and sum) and thus apply Vieta's formulas in $O(n^2)$ time. – John Do Oct 4 '18 at 16:08
• @JohnDo, I do not think I understand "another way" of yours. How do you get, for example, from $x_1+x_2$ to $x_1x_2$? Or from $x_1+x_2+x3$ to $x_1x_2+x_2x_3+x_3x_1$? – John L. Oct 4 '18 at 16:54
• Nevermind, I was actually wrong, I was imagining something like $(x_1+x_2)\times x_1 + (x_1+x_2)\times x_2$, which doesn't work... – John Do Oct 4 '18 at 18:46