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

Problem Detail: 

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.

Asked By : user2512046

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23037