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
