Let \(g,f:\mathbb N\mapsto\mathbb R\) be two functions of natural numbers to real numbers. We say that \(f\) has order of \(g\) and write \[f=\mathcal O(g),\quad\quad( * )\] if and only if there is a positive constant \(c\in\mathbb R_+\) such that for all sufficiently large \(n\in\mathbb N\), i.e. all \(n \ge N( c )\)1 the absolute values of both functions fulfill the following relation:
\[|f(n)|\le c|g(n)|\]
Note: The use of "\(=\)" in \(( * )\) is somewhat different from a usual equation. This notation does not mean that \(f\) "equals" \(\mathcal O(g)\). It rather means that, while \(f\) is a function, \(\mathcal O(g)\) is a whole class of functions \(g\) such that for each such \(g\) there exists constants \(c\) and \(N(c)\) such that \(|f(n)|\le c|g(n)|\) for all \(n\ge N( c )\).
The number \(N( c )\) depends on the constant \(c\). ↩
