1. A means of indicating the way a function varies in magnitude as its argument tends to some limits, usually zero or infinity. More precisely if there is some constant K such that
for all
x ≥
x1, then we say that
f(
x) is order ϕ(
x) as
x tends to infinity, and we write
For example,
If
then we write
For example,
Both these notations are statements about maximum magnitude and do not exclude
f from being of smaller magnitude. For example,
is perfectly valid, but equally
If
then we write
For example,
The term order and the O notation is used in numerical analysis, particularly in discretization methods. In ordinary differential equations, if
h denotes the stepsize, then a method (or formula) has order
p (a positive integer) if the global discretization error is O(
hp). This means that as the step size
h is decreased, the error goes to zero at least as rapidly as
hp. Similar considerations apply to partial differential equations. High-accuracy formulas (order up to 12 or 13) are sometimes used in methods for ordinary differential equations. For reasons of computational cost and stability, low-order formulas tend to be used in methods for partial differential equations.
The term is also used to refer to the speed of convergence of iteration schemes, for example Newton’s method for computing the zero of a function f(x). Subject to appropriate conditions, Newton’s method converges quadratically (or has order of convergence 2), i.e. an approximate squaring of the error is obtained in each iteration.
2. Another name for operation code.