Proposition: Calculation Rules for the Big O Notation

Let \(g,f\), be two functions of natural numbers to real numbers and let \(c > 0\) be a real number, formally \(g,f:\mathbb N\mapsto\mathbb R\), \(c\in\mathbb R_+\). For the big \(\mathcal O\)-Notation, the following rules of calculation hold:

\((1)\) \(f=\mathcal O(f)\)

\((2)\) \(c\cdot \mathcal O(f)=\mathcal O(f)\) for all \(c > 0\).

\((3)\) \(\mathcal O(\mathcal O(f))=\mathcal O(f)\)

\((4)\) \(\mathcal O(f)\cdot \mathcal O(g)=\mathcal O(f\cdot g)\)

\((5)\) \(\mathcal O(f\cdot g)=|f|\cdot \mathcal O(g)\)

\((6)\) If \(|f(n)|\le |g(n)|\) for sufficiently large \(n\), then \(\mathcal O(f)= \mathcal O(g)\).

Proofs: 1

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




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