Horner's Method

Evaluate A₀ + A₁x + A₂x² + ⋯ + Aₙxⁿ in O(n) time.

1. Choose a polynomial

A₀ A₁ A₂ A₃

Ordinary form

Horner form

2. Trace the multiply-add process

Start with the highest coefficient, then repeatedly do result = result × x + next coefficient.

Final result

Arithmetic work

n mult + n add

Only one multiply and one addition per coefficient.

Time complexity

O(n)

One pass from Aₙ down to A₀.

Interview derivation

Factor out x repeatedly:

A₀ + A₁x + A₂x² + A₃x³

= A₀ + x(A₁ + A₂x + A₃x²)
= A₀ + x(A₁ + x(A₂ + A₃x))
= ((A₃x + A₂)x + A₁)x + A₀

The key observation is that every inner partial result can be reused instead of recomputing powers such as x², x³, ….

result = A[n]

for i = n - 1 down to 0:
    result = result * x + A[i]

return result

So for a degree-n polynomial, Horner's method uses exactly n multiplications and n additions, giving O(n) time and O(1) extra space.