[rerdavies]

The most efficient implementation of Lagrange Interpolators is O(N).

Calculate the left Product(0..i-1) of each term in left-to-right order, and the Product(i+1..N-1) of each term in right-to-left order. Your mileage may vary on a GPU.

[steppi]

I think you're talking about evaluating the interpolating polynomial at a single value, but others are talking about getting all of the coefficients of the interpolating polynomial.

[pkhuong]

GP is referring to https://en.wikipedia.org/wiki/Lagrange_polynomial

Build a table left[j] of product-of-ratios for i < j, and another right[k] for i > k, each in linear-time, and combine the two to find the product-of-ratio for i != m in linear time as well.

[steppi]

Right, and if we are trying to get all coefficients and are thus performing the polynomial multiplications symbolically, then performing the multiplications naively will take O(n^2) time but using FFT allows it to be done in O(n log n) time.

[rerdavies]

:-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization.

https://news.ycombinator.com/edit?id=34720462

[credit_guy]

I'm not aware of any algorithm for Lagrange interpolation that is O(N), and wikipedia does not know one either.

What do you mean by left product and right product?