Horner’s Method

25/10/2016

It’s not like evaluating polynomial is something that comes up that frequently in the average programmer’s day. In fact, almost never, but it brings up a number of interesting questions, such as, how do we evaluate it very efficiently and how much of a simplification in the computation is actually a simplification?

The generic polynomial has the form

$a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n$ .

If we evaluate this naïvely, we end up doing $O(n^2)$ multiply and $O(n)$ additions. Even using the fast exponentiation algorithm, we still use $O(n \lg n)$ multiplies. But we can, very easily, get down to $O(n)$ .