I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following:

Let $F(x)$ be given as a product $F(x) = \prod_{i=0}^{n} (x - a_i)$. Transforming $F(x)$ to its canonical form by consecutively multiplying the $i$th monomial with the product of the first $i-1$ monomials requires $\Theta(n^2)$ multiplications of coefficients.

A canonical form of a polynomial is $\sum_{i=0}^{n} c_i x_i$.

Why does this take $\Theta(n^2)$ time?

  • $\begingroup$ How many multiplications does it take to multiply the $i$-th monomial with the (already computed) product of the first $i-1$? $\endgroup$ – Tom van der Zanden Jan 20 '19 at 12:09
  • $\begingroup$ It seems you have accidentally created two accounts (based on the suggested edit with the same name. If you use the same account as you created the question with, you can edit your question immediately). See the help center for information on how to merge them. $\endgroup$ – Discrete lizard Jan 20 '19 at 17:54
  • 1
    $\begingroup$ Could you mention the name of the textbook where you found this problem? Thanks! This is useful for us to get some context, and useful for others find this question. $\endgroup$ – Discrete lizard Jan 20 '19 at 17:56

Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula: $$ (x-c) \sum_{i=0}^d b_i x^i = (-cb_0) x^0 + \sum_{i=1}^d (b_{i-1}-cb_i)x^i + b_dx^d. $$ If you compute $(x-a_1)\cdots(x-a_n)$ by successively multiplying the terms, i.e. by computing $P_1 = x-a_1$ and $P_{d+1} = P_d(x-a_{d+1})$ for $1 \leq d \leq n-1$, then you need this many multiplications: $$ 1+2+\cdots+(n-1) = \frac{n(n-1)}{2} = \Theta(n^2). $$

| cite | improve this answer | |

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.