Lagrange Interpolation for Polynomial Construction and Evaluation
Given a polynomial (f) of degree (k) and (k+1) data points ((x_i, y_i)) where (f(x_i) = y_i), the goal is to reconstruct (f). While Gaussian elimination solves this in (O(k^3)), Lagrange inteprolation provides an (O(k^2)) construction: [ f(x) = \sum_{i=1}^{k+1} y_i \cdot \prod_{\substack{j=1 \ j \ne...