2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Do Oct 4 '18 at 16:08
  • $\begingroup$ @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$? $\endgroup$ – John L. Oct 4 '18 at 16:54
  • $\begingroup$ 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... $\endgroup$ – John Do Oct 4 '18 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.