Calcul des coefficients d'un polynôme à partir de ses racines

Question

Laisser $ P $ être un polynôme polynomial monic donné par ses racines:$$ p (x) = (x-x_1) Times ... Times (x-x_n) $$

Quelle est la complexité asymptotique minimale pour calculer son expansion de la forme:$$ a_nx ^ n + ... + a_0 $$

---

Ce que j'ai trouvé jusqu'à présent est Les formules de Vieta qui donnent une expression de chacun $ a_k $ comme une somme sur $ 1 leq i_1 <... <i_ {nk} leq n $. Cela suggérerait la complexité de l'informatique $ k $Le coefficient est quelque chose comme $ {n-1 choisir nk-1} = {n-1 choisir k} = o (n ^ k) $, ce qui rend la complexité totale des fous (je suppose que quelque chose comme $ O (n ^ n) $).

Pourtant, la présentation de mon professeur suggère que c'est un $ O (n ^ 2) $, qui ne correspond pas du tout à mon calcul.