Let F be the field. We consider a polynomial over the field. . p:=\cases{ F\to F\\ x\to p(x):=a_nx^n + \ldots + a_1x + a_0,\\ }
where a_0,a_1,\ldots,a_n\in F and assume that p is a polynomial of degree n, i.e. a_n\neq 0. Horner scheme is an algorithm for calculating the value p(x_0) at a specific value x\in F. The algorithm \mathtt{horner}(n,x,a) requires \mathcal O(n) (worst case and average case) multiplication and addition operations.
def horner(n,a,x): h = a[n] for i in range(n-1, -1, -1): h = h*x + a[i]
return h
a = [4, 3, 2, 1] n = len(a)-1 x = 1 print(horner(n,a,x))
Definitions: 1
