Polynomial expansion

Question

Question from the Probability and Computing book by Mitzenmacher M. and Upfal E.

Given is the following polynomial: $$F(x)=\prod_{i=1}^d(x-a_i)$$

Then the book says:

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(d^2)$ multiplications of coefficients.

Did the authors mean to write $2^d$? If not, what does $\Theta(\cdot)$ mean then?

Answer 1

No, they meant $\Theta(d^2)$. They describe a process for going from a polynomial of degree $k$ to one of degree $k+1$, or rather, from the coefficients of a degree $k$ polynomial to the coefficients of a degree $k+1$ polynomial. This takes $O(k)$ multiplications, and $\sum_{k=1}^dO(k) = \Theta(d^2)$.