Complexity of evaluating Lagrange polynomial
Mia Lopez 
Given a set of n + 1 data points $(x_i, f(x_i))$The langrange polynomial is given by:$$\sum_{i=0}^n f(x_i) \frac{(x-x_1)\cdot... (x-x_{i-1})(x-x_{i+1}) \cdot....\cdot(x-x_n)}{w_i}$$ with $w_i:= (x_i-x_1)\cdot ...\cdot(x_i-x_{i-1})(x_i-x_{i+1})\cdot....\cdot(x_i-x_n)$
To compute that you consider $$(x-x_1)\cdot...\cdot(x-x_n) \sum_{i=0}^n f(x_i) \frac{1}{w_i(x-x_i)}$$
Why does this computation leads to time complexity $O(n)$?
$\endgroup$ 14 Reset to default
