[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?