Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top