1.2. Order Notation

Let \(f,g:\mathbb R\rightarrow\mathbb R\) be two functions. We say that \(f(n) = O(g(n))\), read as “\(f\) is big-oh of \(g\)” or “\(f\) is of order \(g\)”, if there is a positive constant \(C\) such that

\[\vert f(n)\vert\leq C\vert g(n)\vert\]

for all sufficiently large \(n\). For example,

\[2n^3 + 3n^2 + n = O(n^3)\]

because as \(n\) becomes large, the terms of order lower than \(n^3\) become relatively insignificant. While the above definition is based on the function argument increasing in magnitude, the order notation can also be defined when the function argument keeps decreasing in magnitude. Indeed, in many applications we are interested in the behavior as some quantitiy \(h\) (such as a step size or mesh spacing) becomes very small. We say that

\[f(h) = O(g(h))\]

if there is a positive constant \(C\) such that

\[\vert f(h)\vert \leq C\vert g(h)\vert\]

for all sufficient small \(h\). For example,

\[\frac{1}{1-h} = 1+h+h^2+h^3+\ldots = 1+h+O(h^2)\]

because as \(h\) becomes small, the omitted terms beyond \(h^2\) become relatively insignificant. Note that the above two definitions are equivalent if \(h=1/n\).