stylistic:style_transfer, stylistic:tone
Efficiency

Evaluation using the monomial form of a degree n {\displaystyle n} polynomial requires at most n {\displaystyle n} additions and (n 2 + n) / 2 {\displaystyle (n^{2}+n)/2} multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. The cost can be reduced to n {\displaystyle n} additions and 2 n − 1 {\displaystyle 2n-1} multiplications by evaluating the powers of x {\displaystyle x} by iteration.

If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately 2 n {\displaystyle 2n} times the number of bits of x {\displaystyle x}: the evaluated polynomial has approximate magnitude x n {\displaystyle x^{n}}, and one must also store x n {\displaystyle x^{n}} itself. By contrast, Horner's method requires only n {\displaystyle n} additions and n {\displaystyle n} multiplications, and its storage requirements are only n {\displaystyle n} times the number of bits of x {\displaystyle x}. Alternatively, Horner's method can be computed with n {\displaystyle n} fused multiply–adds. Horner's method can also be extended to evaluate the first k {\displaystyle k} derivatives of the polynomial with k n {\displaystyle kn} additions and multiplications.

Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. Alexander Ostrowski proved in 1954 that the number of additions required is minimal. Victor Pan proved in 1966 that the number of multiplications is minimal. However, when x {\displaystyle x} is a matrix, Horner's method is not optimal.

This assumes that the polynomial is evaluated in monomial form and no preconditioning of the representation is allowed, which makes sense if the polynomial is evaluated only once. However, if preconditioning is allowed and the polynomial is to be evaluated many times, then faster algorithms are possible. They involve a transformation of the representation of the polynomial. In general, a degree- n {\displaystyle n} polynomial can be evaluated using only ⌊ n /2 ⌋ +2 multiplications and n {\displaystyle n} additions.