Expansión polinómica

Question

Pregunta del Probabilidad y computación libro de Mitzenmacher M. y Upfal E.

Dado es el siguiente polinomio: $$F(x)=\prod_{i=1}^d(x-a_i)$$

Entonces el libro dice:

Transformando $F(x)$ a su forma canónica multiplicando consecutivamente el $i$ monomio con el producto del primer $i-1$ monomios requiere $\Theta(d^2)$ multiplicaciones de coeficientes.

¿Querían los autores escribir $2^d$ ? Si no es así, ¿qué hace $\Theta(\cdot)$ ¿entonces?

Answer 1

No, se referían a $\Theta(d^2)$ . Describen un proceso para pasar de un polinomio de grado $k$ a uno de grado $k+1$ o, más bien, de los coeficientes de un grado $k$ polinomio a los coeficientes de un grado $k+1$ polinomio. Esto toma $O(k)$ multiplicaciones, y $\sum_{k=1}^dO(k) = \Theta(d^2)$ .