What is the use of Horner's Method?

Here is Wikipedia's explanation of Horner's Method:

Given the polynomial

$$p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,$$

where $a_0, \ldots, a_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x$, say $x_0$.

To accomplish this, we define a new sequence of constants as follows:

\begin{align} b_n & := a_n \\ b_{n-1} & := a_{n-1} + b_n x_0 \\ & {}\ \ \vdots \\ b_0 & := a_0 + b_1 x_0. \end{align}

Then $b_0$ is the value of $p(x_0)$.

To see why this works, note that the polynomial can be written in the form

$$p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)).$$

Thus, by iteratively substituting the b_i into the expression,

\begin{align} p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\ & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\ & {} \ \ \vdots \\ & = a_0 + x_0(b_1) \\ & = b_0. \end{align}

Question:

Is the point of this algorithm that we can now evaluate $p(x_0)$ without having to ever evaluate any of the values $x_0^2, \ldots, x_0^n$, and instead, we are able to just just iteratively compute $b_n$ through $b_0$, where by the time we eventually get to $b_0$ we are finally able to evaluate $p(x_0)$?

If this is the case, why is this useful? Why not just compute $p(x_0)$ the normal way?

EDIT: Is it true that using Horner's rule to compute a polynomial of degree $n$ takes running time from $\Theta(n^2)$ down to $\Theta(n)$?

• You said it yourself. – Yuval Filmus Aug 28 '15 at 15:10

You have the polynomial $ax^3 + bx^2 + cx + d$. Computing directly you have six multiplications: (a * x * x * x, b * x * x, c * x). With Horner $((ax + b)x + c)x + d$ you have three multiplications: (a * x, first parenthesis * x, second parenthesis * x)