I have been recently learning about polynomials and ways of presenting them and I have encountered a problem, which is converting a Newton polynomial to the power form in the efficient way.
Newton polynomial is expressed as $$w = a_0 + \sum_{i=1}^{n}a_i\prod_{j=0}^{i-1}(x-x_j)$$ where $a_i$ are coefficients of Newton polynomial and $x_j$ are given $x$ coordinates from points $(x_0, y_0), (x_1, y_1), \dots, (x_{i-1}, y_{y-1})$. Power form is expressed as: $$w = \sum_{k=0}^{n}a_kx^k$$
If we wanted to go from Newton's form to power form, we would have to rewrite the polynomial in its expanded form, so $w = a_0 + a_1 (x-x_0) + \dots + a_n (x-x_0)(x-x_1) \dots (x - x_{n-1})$ and then use all the data we have to complete calculations. The problem is that doing it by hand is pretty slow process, especially for higher-degree polynomials (even $\Pi_4$ would take a while).
My question is how to get power form from Newton polynomial and what time complexity does that algorithm have in big $\mathcal{O}$ notation?