Hacker News Reader

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.

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.

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.

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

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

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?