${\displaystyle \Theta }$ -Notation

Beweis

Zu zeigen: ${\displaystyle \Theta (f(n))\subseteq O(f(n))\cap \Omega (f(n))~und~\Theta (f(n))\supseteq O(f(n))\cap \Omega (f(n))}$

${\displaystyle \Theta (f(n))\subseteq O(f(n))\cap \Omega (f(n)):}$

Zeige ${\displaystyle g(n)\in \Theta (f(n))\Rightarrow g(n)\in O(f(n))\cap \Omega (f(n)).}$

• ${\displaystyle g(n)\in \Theta (f(n))\Rightarrow \exists c_{1},c_{2},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)\geq c_{2}f(n)}$

${\displaystyle \Rightarrow \exists c_{1},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)~und~\exists c_{2},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)\geq c_{2}f(n)}$

${\displaystyle \Rightarrow g(n)\in O(f(n))~und~g(n)\in \Omega (f(n))}$

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

Beispiel 1

Wir stellen uns die Frage, ob ${\displaystyle n^{2}\in O(n^{3})}$ bzw. ob ${\displaystyle n^{3}}$ eine obere Schranke für ${\displaystyle n^{2}}$ ist. Die Antwort ist ja. Die Begründung dazu lautet folgendermaßen:

${\displaystyle n_{0}=1,c=1}$

${\displaystyle \Rightarrow n^{2}\leq n^{3}}$

${\displaystyle \Rightarrow 1\leq n\ {\text{für}}\ n\geq 1}$

Beispiel 2

Wir stellen uns die Frage, ob ${\displaystyle n^{3}\in O(n^{2})}$ bzw. ob ${\displaystyle n^{2}}$ eine obere Schranke für ${\displaystyle n^{3}}$ ist. Die Antwort ist nein. Beweisen kann man das durch Widerspruch. Unsere Annahme ist: ${\displaystyle \exists c,n_{0}\in \mathbb {N} :n^{3}\leq c\cdot n^{2},{\text{für alle }}n>n_{0}}$

${\displaystyle n^{3}\leq c\cdot n^{2},{\text{für alle }}n>n_{0}}$

${\displaystyle \Rightarrow n\leq c,{\text{für alle }}n>n_{0}}$

Wähle ${\displaystyle n=c+n_{0}\Rightarrow c+n_{0}\leq c}$ Widerspruch!!