Definition: Big O Notation

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 )\).

Proofs: 1
Propositions: 2

Thank you to the contributors under CC BY-SA 4.0!




  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition


  1. The number \(N( c )\) depends on the constant \(c\).