Für beliebige Funktionen f,g gilt:
${\displaystyle O(f(n)+g(n))=O(max(f(n),g(n))}$

${\displaystyle t(n)\in O(f(n)+g(n))\Rightarrow t(n)\in O(max(f(n),g(n)))}$

${\displaystyle t(n)\in O(f(n)+g(n))\Leftarrow t(n)\in O(max(f(n),g(n)))}$

Als erstes machen wir den Beweis nach rechts (${\displaystyle \Rightarrow }$)

${\displaystyle \exists c,n_{0}\in \mathbb {N} :t(n)\leq c\cdot (f(n)+g(n))\ \forall n>n_{o}}$

${\displaystyle \Rightarrow t(n)\leq 2\cdot c\cdot max(f(n),g(n))\ \forall n>n_{0}}$

${\displaystyle \Rightarrow t(n)\in O(max(f(n)),g(n)))}$

nun der Beweis nach links (${\displaystyle \Leftarrow }$)

${\displaystyle \exists c,n_{0}\in \mathbb {N} :t(n)\leq c\cdot (max(f(n),g(n)))\ \forall n>n_{0}}$

${\displaystyle \Rightarrow t(n)\leq c\cdot (f(n)+g(n))\ \forall n>n_{0}}$

${\displaystyle \Rightarrow t(n)\in O(f(n),g(n))}$

${\displaystyle O(n^{4}+n^{2})=O(n^{4})}$

${\displaystyle O(n^{4}+4\cdot n^{3})=O(n^{4})}$

${\displaystyle O(n^{4}+2^{n})=O(2^{n})}$

1. ${\displaystyle O(f(n))\subseteq O(g(n))\ {\text{genau dann wenn }}f(n)\in O(g(n))}$
2. ${\displaystyle O(f(n))=O(g(n))\ {\text{genau dann wenn }}f(n)\in O(g(n))\land g(n)\in O(f(n))}$
3. ${\displaystyle O(f(n))\subset O(g(n))\ {\text{genau dann wenn }}f(n)\in O(g(n))\land g(n)\notin O(f(n))}$

Beweis zu 1. nach rechts (${\displaystyle \Rightarrow }$)

${\displaystyle O(f(n))\subseteq O(g(n))\Rightarrow f(n)\in O(g(n))}$

${\displaystyle f(n)\in O(f(n))\subseteq O(g(n))\Rightarrow f(n)\in O(g(n))}$

Beweis zu 1. nach links (${\displaystyle \Leftarrow }$)

${\displaystyle O(f(n))\subseteq O(g(n))\Leftarrow f(n)\in O(g(n))}$

${\displaystyle f(n)\in O(g(n))\Rightarrow \exists c_{0},n_{0}\in \mathbb {N} :f(n)\leq c_{0}\cdot g(n)\ \forall n>n_{0}}$ (siehe Definition)

und sei t(n) ein beliebiges Element der Menge O(f(n))

${\displaystyle t(n)\in O(f(n))\Rightarrow \exists c_{1},n_{1}\in \mathbb {N} :t(n)\leq c_{1}\cdot f(n)\ \forall n>n_{1}}$ (siehe Definition)

${\displaystyle \Rightarrow t(n)\leq c_{1}\cdot f(n)\leq c_{1}\cdot c_{0}\cdot g(n)\ \forall n>max(n_{0},n_{1})}$

${\displaystyle t(n)\in O(f(n))\Rightarrow t(n)\in O(g(n))}$

${\displaystyle O(f(n))\subseteq O(g(n))}$ (Definition der Teilmenge, da t(n) ein beliebiges Element ist)

${\displaystyle O(n^{2})=\{n^{2},2n^{2}-6,3n^{2}+5,{\frac {1}{2}}n^{2}+8,...\}}$

Damit ist

${\displaystyle (3n^{2}+5)\in O(n^{2})}$

${\displaystyle O(3n^{2}+5)\subseteq O(n^{2})}$

${\displaystyle O(3n^{2}+5)=\{n^{2},2n^{2}-6,3n^{2}+5,{\frac {1}{2}}n^{2}+8,...\}}$

Damit ist

${\displaystyle n^{2}\in O(3n^{2}+5)}$

${\displaystyle O(n^{2})\subseteq O(3n^{2}+5)}$

Damit ist

${\displaystyle O(n^{2})=O(3n^{2}+5)}$

Falls ${\displaystyle f(n)\in O(g(n))~und~g(n)\in O(h(n))}$, dann ist auch ${\displaystyle f(n)\in O(h(n))}$. 

${\displaystyle f(n)\leq c_{0}\cdot g(n)\ \forall n>n_{0}~und}$

${\displaystyle g(n)\leq c_{1}\cdot h(n)\ \forall n>n_{1}~und}$

${\displaystyle \Rightarrow f(n)\leq c_{0}\cdot g(n)\leq c_{0}\cdot c_{1}\cdot h(n)\ \forall n\geq max(n_{0},n_{1})}$

Dabei ist ${\displaystyle c_{0}\cdot c_{1}}$ eine Konstante.

${\displaystyle O(n^{2})=O(3n^{2})=O({\frac {1}{2}}n^{2})}$

${\displaystyle O(n^{2})\subseteq O(3n^{2})\subseteq O({\frac {1}{2}}n^{2})}$

${\displaystyle O(n^{2})\subseteq O(n^{2,5})\subseteq O(n^{3})}$

${\displaystyle O(n^{2})\subset O(n^{2,5})\subset O(n^{3})}$

1. ${\displaystyle lim_{n\to \infty }(f(n)/g(n))=c,c>0\Rightarrow O(f(n))=O(g(n))}$
2. ${\displaystyle lim_{n\to \infty }(f(n)/g(n))=0\Rightarrow O(f(n))\subset O(g(n))}$

Ein häufiges Problem sind Grenzwerte der Art ${\displaystyle {\frac {\infty }{\infty }}}$ oder ${\displaystyle {\frac {0}{0}}}$ Bei diesem Problem kann man als Ansatz die Regel von de l'Hospital verwenden.

Satz(Regel von de L'Hospital) ${\displaystyle x\to \infty }$
Seien f und g auf dem Intervall ${\displaystyle [\alpha ,\infty )}$ differenzierbar.
Es gelte ${\displaystyle lim_{x\to \infty }f(x)=lim_{x\to \infty }g(x)=0(bzw.=\infty )}$ 
und es existiere ${\displaystyle lim_{x\to \infty }{\frac {f'(x)}{g'(x)}}}$.
Dann existiert auch ${\displaystyle lim_{x\to \infty }{\frac {f(x)}{g(x)}}}$ und es gilt:
${\displaystyle lim_{x\to \infty }{\frac {f'(x)}{g'(x)}}=lim_{x\to \infty }{\frac {f(x)}{g(x)}}}$

1. ${\displaystyle f(n)=3n+5,g(n)=n}$

${\displaystyle lim_{n\to \infty }{\frac {3n+5}{n}}\Rightarrow lim_{n\to \infty }{\frac {3}{1}}=3>0\Rightarrow O(3n+5)=O(n)}$

2. ${\displaystyle f(n)=n^{2}+5,g(n)=n^{3}}$

${\displaystyle lim_{n\to \infty }{\frac {n^{2}+5}{n^{3}}}\Rightarrow lim_{n\to \infty }{\frac {2n}{3n^{2}}}\Rightarrow lim_{n\to \infty }{\frac {2}{6n}}=0\Rightarrow O(n^{2}+5)\subset O(n^{3})}$

Beim zweiten Beispiel musste die Regel von de l'Hospital wiederholt angewandt werden.

Gibt es immer eine Ordnung zwischen den Funktionen? Es gibt Funktionen f und g mit ${\displaystyle f(n)\notin O(g(n))~und~g(n)\notin O(f(n))}$. Ein Beispiel sind die Funktionen sin(n) und cos(n).

Für alle ${\displaystyle m\in \mathbb {N} ~gilt:O(n^{m})\subseteq O(n^{m+1})}$

Wir nehmen an, dass ${\displaystyle s(n)\in O(n^{k})}$,

das heißt ${\displaystyle \exists c,n_{0},\forall n>n_{0}:s(n)\leq c\cdot n^{k}}$.

Aber es muss auch ${\displaystyle s(n)\notin O(n^{k+1})}$ gelten,

das heißt ${\displaystyle \exists n>n_{0}:s(n)>c\cdot n^{k+1}}$

${\displaystyle \Rightarrow \exists n>n_{0}:und~n<1}$