On the complexity of algorithms for the translation of polynomials

Research paper by A. G. Akritas, S. D. Danielopoulos

Indexed on: 01 Mar '80Published on: 01 Mar '80Published in: Computing


Three algorithms for computing the coefficients of translated polynomials are discussed and compared from the point of view of complexity. The two classical translation algorithms based on explicit application of the Taylor expansion theorem and the Ruffini-Horner method, respectively, have complexityO (n2). A third algorithm based on the fast Fourier transform is shown to have complexityO (n logn). However, when the cost of arithmetic operations is explicitly taken into consideration, the Ruffini-Horner algorithm is one order of magnitude better than the one based on the Taylor expansion and competes quite well with the algorithm based on the fast Fourier transform.