Show Summary Details

Quick Reference

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 |f(x)| ≤ Kϕ(x) for all xx1, then we say that f(x) is order ϕ(x) as x tends to infinity, and we write f(x) = O(ϕ(x) For example, 100x2 + 100x + 2 = O(x2) as x → ∞ If then we write f(x) = o(g(x) For example, x = o(x2) as x → ∞ Both these notations are statements about maximum magnitude and do not exclude f from being of smaller magnitude. For example, x = O(x2) is perfectly valid, but equally x = O(x) If then we write f(x) ≅ kg(x) as xa For example, 10x2 + x + 1 ≅ 10x2 as x → ∞ 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.

|f(x)| ≤ Kϕ(x)

f(x) = O(ϕ(x)

100x2 + 100x + 2 = O(x2)

as x → ∞

f(x) = o(g(x)

x = o(x2) as x → ∞

x = O(x2)

x = O(x)

f(x) ≅ kg(x) as xa

10x2 + x + 1 ≅ 10x2

as x → ∞

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.

2Another name for operation code.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.