patternMinor
Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?
Viewed 0 times
thetacanonicalwhymultiplicationpolynomialcoefficientforformrequired
Problem
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?
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?
Solution
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).
$$
$$
(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).
$$
Context
StackExchange Computer Science Q#103131, answer score: 3
Revisions (0)
No revisions yet.