Calcolo dei coefficienti di un polinomio dalle sue radici

Question

Permettere $ P $ essere un polinomio polinomiale monico dato dalle sue radici:$$ p (x) = (x-x_1) tempes ... tempes (x-x_n) $$

Qual è la complessità minima asintotica per calcolare la sua espansione della forma:$$ a_nx^n+...+a_0 $$

---

Quello che ho trovato finora sono Le formule di Vieta che danno un'espressione di ciascuno $ a_k $ Come somma $ 1 leq i_1 <... <i_ {nk} leq n $. Ciò suggerirebbe la complessità del calcolo del $ k $Il coefficiente di Th è qualcosa di simile $ {n-1 scegli nk-1} = {n-1 scegli k} = o (n^k) $, rendendo così la complessità totale dei viaggi (immagino qualcosa di simile $ O (n^n) $).

Eppure la presentazione del mio insegnante suggerisce che è un $ O (n^2) $, che non corrisponde affatto al mio calcolo.