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 &amp; := a_n \\
b_{n-1} &amp; := a_{n-1} + b_n x_0 \\
&amp; {}\  \  \vdots \\
b_0 &amp; := 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) &amp; = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\
&amp; = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\
&amp; {} \ \  \vdots \\
&amp; = a_0 + x_0(b_1) \\
&amp; = 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)$?
Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way.

Example:  


  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)


It is important to remember that in floating point calculations results from these two methods (direct and Horner) will differ.