 Arithmetic complexity

Arithmetic complexity counts arithmetic operations under an explicitly stated computational model. One may count additions, subtractions, multiplications and divisions over a specified field as unit operations, or distinguish their costs. This exposes algebraic structure without yet accounting for how each number is represented.

For a degree-$n$ polynomial $a_0+a_{1}x+\cdots +a_n{x}^n$, Horner's method sets $b_n=a_n$ and $b_i=a_i+x{b}_{i+1}$ for $i=n-1,\dots ,0$. It returns $b_0$ using $n$ multiplications and $n$ additions. Repeatedly expanding each power independently would obscure this reuse of earlier work. An arithmetic circuit represents such dependencies as a finite network of arithmetic operations.

Bit complexity asks an additional question: how much work is required to perform those operations on the encoded numbers? Multiplying two large integers is one arithmetic operation but requires processing their bits. Intermediate numerators and denominators can also grow. Conversely, a small arithmetic-operation count does not bound round-off error; the numerical stability of an evaluation scheme is a separate property.