# Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations?

I have been trying to understand the difference between normal polynomial evaluation and horner's method. usually it takes 3n-1 operations while horner's method reduces it to 2n operations. I tried a couple of explanations but they were too theoritical. I would be glad if somebody comes up with a decent and simple explanation.

• What is "normal polynomial evaluation" in your mind ?
– user16034
Commented Mar 26, 2014 at 8:24
• @YvesDaoust The OP actually gives the answer to your question indirectly. If he factors the computation of powers of $x$, it takes n-1 products for the powers of $x$, and 2n operations for the rest, making the total of 3n-1 indicated in the question. If you do not factor the powers of $x$, the total cost for computing them is n(n-1)/2, i.e.,the sum of the first n-1 integers, to be added to the other 2n operations. So "normal polynomial evaluation" must be the former. Commented Mar 26, 2014 at 13:15
• @babou: I know. I wanted to hear that from the OP's mouth...
– user16034
Commented Mar 26, 2014 at 14:13
• @YvesDaoust Why? Commented Mar 26, 2014 at 15:59
• @babou: so that he realizes that saying "normal" is actually undefined and forces the reader to "reverse engineer" his question. For most beginners, the "normal" way is by invoking the $pow$ function on every term.
– user16034
Commented Mar 27, 2014 at 6:59

Let's compute the polynomial $2+3x+x^2+15x^3$ using Horner's method: $$2 + x(3 + x(1 + 15x)).$$ The complete set of steps is \begin{align*} &t_1 \to 15 \times x \\ &t_2 \to t_1 + 1 \\ &t_3 \to t_2 \times x \\ &t_4 \to t_3 + 3 \\ &t_5 \to t_4 \times x \\ &t_6 \to t_5 + 2 \end{align*} Compare this to the "trivial" method: \begin{align*} &t_1 \to x \times x \\ &t_2 \to t_1 \times x \\ &t_3 \to 15 \times t_2 \\ &t_4 \to 3 \times x \\ &t_5 \to 2 + t_4 \\ &t_6 \to t_5 + t_1 \\ &t_7 \to t_6 + t_3 \end{align*} Here the idea is to compute the powers $1,x,x^2,x^3$ and then take the linear combination corresponding to the polynomial. Since one of the coefficients is $1$ (coefficient of $x^2$), we only need $7$ rather than $8$ operations.

By computing powers, $2+3x+6x^2+15x^3+8x^4$ is obtained using $2d-1 \color{red}{\times }$ and $d\color{red}{+}$, as:

$p:=2\space \space \rightarrow 2$

$z:=\space \space \space \space \space \space \space x, \space p:=p\color{red}{+}\space \space 3\color{red}{\times }z\space \space \rightarrow 2+3x$

$z:=z\color{red}{\times} x, \space p:=p\color{red}{+}\space \space 6\color{red}{\times}z\space \space \rightarrow 2+3x+6x^2$

$z:=z\color{red}{\times}x, \space p:=p\color{red}{+}15\color{red}{\times}z\space \space \rightarrow 2+3x+6x^2+15x^3$

$z:=z\color{red}{\times}x, \space p:=p\color{red}{+}\space \space 8\color{red}{\times}z\space \space \rightarrow 2+3x+6x^2+15x^3+8x^4$

By Horner's method, $8x^4+15x^3+6x^2+3x+2$ is computed using $d\color{red}{\times }$ and $d\color{red}{+}$, as:

$p:=8\space \space \rightarrow 8$

$p:= p\color{red}{\times}x\color{red}{+}15\space \space \rightarrow 8x\space \space +15$

$p:= p\color{red}{\times}x\color{red}{+}\space \space 6\space \space \rightarrow 8x^2+15x\space \space +6$

$p:= p\color{red}{\times}x\color{red}{+}\space \space 3\space \space \rightarrow 8x^3+15x^2+6x\space \space +3$

$p:= p\color{red}{\times}x\color{red}{+}\space \space 2\space \space \rightarrow 8x^4+15x^3+6x^2+3x+2$

The trick is that every time you multiply by $x$, the multiply applies to all terms and you needn't compute the powers of $x$ separately.

What happens is that the product of the coefficient $a_i$ with $x^i$ is combined with the computation of the powers of x. This is based on different uses of distributivity of multiplication for addition, with repeated uses of the following transformation, which saves each time one multiplication: $$A_ix+a_ix \;\Rightarrow\;(A_i+a_i)x$$ Here $A_i$ stands for the higher power terms (with index greater than $i$) already added together, up to a factor $x^{i-1}$ that is still to be computed in the Horner evaluation: $$A_i=\sum_{j=i+1}^{n}a_jx^{j-i}$$ This transformation is applied $n-1$ times, thus saving as many multiplications.

## More details

The transformation of the polynomial uses the following basic step: $$\sum_{i=0}^n a_ix^i = \Big(\sum_{i=0}^{n-1} a_{i+1}x^{i}\Big)x + a_0$$

which you can repeat recursively $n-1$ times to get the Horner formula:

$$\sum_{i=0}^n a_ix^i = ((...((a_nx+a_{n-1})x + a_{n-2})x + ...)+a_1)x+a_0$$

The left-hand side is the traditional representation of polynomials, while the right-hand side is the Horner representation. A first important comment is that the Horner representation is an arithmetic formula that shows explicitly all operations that are performed (though the multiplication operator is not written here for better readability). They can be directly counted on a Horner formula like $$((( a_3 \times x +a_2)\times x+a_1)\times x + a_0)$$ However this is not true of the traditional formulation with powers of x: $$a_3\times x\times x\times x +a_2\times x\times x+a_1\times x+a_0$$ because, in actual practice, the computation of the powers of x is factored, so that each power is computed only once. Consequently, the only products of $x$ by itself that count are those of the higest power of $x$.
The actual computation cannot be represented by a tree structure, hence by a simple arithmetic formula, and in prectice requires one extra variable of storage to keep the successive powers of $x$.
This is what makes the analysis more complex, and it might be more illuminating to compare separately each the two modes of evaluation with the most naive mode that does not factor (share) anything when computing the various powers $x^i$.
[I can attempt to do that on request, but this answer is long enough as it is.]

## Analysis

At each recursive application of the first formula above to obtain the Horner form, we save one multiplication, which totals to a saving of $n-1$ multiplications for the whole transformation.

What happens is that the product of the coefficient $a_i$ with $x^i$ is combined with the computation of the powers of x.

More precisely this uses distributivity of product wrt sum: $ax+bx=(a+b)x$
When you do the sum first, you have 2 operations, instead of 3, saving one multiplication.

It must be objected that when you have $n$ terms, you should save $n-1$ multiplication, for example 3 multiplications when you have 4 terms as in: $ax+bx+cx+dx=(a + b + c +d)x$
This formula gives a saving of $n-1$ multiplications, i.e., 3 in the example.

This would be true if we were comparing with the very naive evaluation of polynomials that does not factor the computation of powers of $x$.
However the situation is here even more subtle, and follow a more complex pattern, where all terms but one contain a product with the same factor $y$, for example $ayx+byx+cyx+dx = (ay + by + cy +d)x$.
This again corresponds to the very naive evaluation of the polynomial, where $y$ is actually equal to $x$.

However, there are other ways of computing this, such as $(a+b+c)yx+dx$. This is precisely the case in the traditional evaluation of the polynomial, when computing only once each power of $x$, thus factoring the computation of $x^i$ for the computation of all $x^j$ such that $j \ge i$. Note also that in the case of the polynomial, we have $y=x$, but it changes nothing.

So the transformation used at each step is better represented (still taking the same four terms example) by the formula: $(a+b+c)yx+dx=((a + b + c)y +d)x$
which replaces three multiplications by only two, thus saving one multiplication at each step of the recursive transformation, independently of the number of terms in the sum.

As the formula is applied $n-1$ times to get the Horner form, we save a total of $n-1$ multiplications.