Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations?
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*}
&amp;t_1 \to 15 \times x \\
&amp;t_2 \to t_1 + 1 \\
&amp;t_3 \to t_2 \times x \\
&amp;t_4 \to t_3 + 3 \\
&amp;t_5 \to t_4 \times x \\
&amp;t_6 \to t_5 + 2
\end{align*}
$$
Compare this to the "trivial" method:
$$
\begin{align*}
&amp;t_1 \to x \times x \\
&amp;t_2 \to t_1 \times x \\
&amp;t_3 \to 15 \times t_2 \\
&amp;t_4 \to 3 \times x \\
&amp;t_5 \to 2 + t_4 \\
&amp;t_6 \to t_5 + t_1 \\
&amp;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.