Evaluating polynomials faster

I was just trying to find the roots of \(f(x) = 4 + 10x + 6x^2 + x^3\) by trying some values of x, when I came up with a better way of evaluating polynomials. Up till then I had been evaluating polynomials by summing the values of monomials. The better way is to rewrite the polynomial above as \(4 + x(10 + x(6 + x(1)))\), evaluate the innermost parenthesis first and work one's way out.

Let the degree of the polynomial be n. The complexity of finding the value of an mth degree monomial is \(\log(m+1)\). By summing the complexities from m = 0 to n we get \(\log 1+\log 2+\log 3+...+\log n+\log (n + 1)\), which is about the same as \(\log(n^n) = n\log n\). The new method on the other hand is linear in n because we only need to multiply and add once more every time n increases by one.

To compute f(-2), we start with the last coefficient, 1, and alternatingly multiply by x and add the coefficient to the left. Our partial results are: 1, -2, 4, -8, 2, -4, 0. Indeed, x = -2 is a root of the polynomial.