The complexity of evaluating interpolation polynomials (Q1081273)

It is well known that the complexity of computing all coefficients of the Lagrangian interpolation polynomial for n nodes and n values is of order n log n. Proving in this paper a more general theorem with respect to the complexity bounds of the tasks of computing the coefficients of the Lagrangian interpolation polynomials, the author derives from this the previous result about the complexity order n log n.