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.