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
