HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
hornercantheoperationsmethodpolynomialstimereducedoeshow

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#23037, answer score: 5

Revisions (0)

No revisions yet.