Number of products required to multiply polynomial coefficients

I am wondering about the claim from the book "Probability and computing" that the number of products required to multiply monomial coefficients is $\Theta(d^2)$, where $d$ is the number of monomials that forms the polynomial
$$P(x) = (x-a_1)(x-a_2)\cdots(x-a_d).$$
I think this answer is wrong and it takes $\Theta(2^d)$ instead.

Could someone explain this, please?

Consider the following algorithm:

• Start with $P = 1$.

• For $i=1,\ldots,d$: replace $P$ with $P \cdot (x - a_i)$.

At step $i$, the polynomial $P$ has degree $i-1$, and so we need to compute
$$
\sum_{j=0}^{i-1} p_j x^j (x - a_i) = \sum_{j=1}^i p_{j-1} x^j - \sum_{j=0}^{i-1} a_i p_j x^j = -a_i p_0 + \sum_{j=1}^{i-1} (p_{j-1} - a_i p_j) x^j + p_{i-1} x^i.
$$
As you can see, this requires $i-1$ products. Summing over all $i$, we obtain $\frac{d(d-1)}{2} = \Theta(d^2)$ products.

In fact, using FFT we can improve on this. FFT multiplies two degree $m$ polynomial using only $\Theta(m\log m)$ products. A straightforward divide and conquer approach results in the following recurrence for the number of products:
$$ T(d) = 2T(d/2) + \Theta(d\log d). $$
The solution is $T(d) = \Theta(d\log^2 d)$.

StackExchange Computer Science Q#149641, answer score: 11