Die exakte Ordnung ${\displaystyle \Theta }$ von f(n) ist definiert als:

${\displaystyle \Theta (f(n))=\{g:\mathbb {N} \to \mathbb {N} |\exists c_{1}\in \mathbb {R} ^{>0},\exists c_{2}\in \mathbb {R} ^{>0},\exists n_{o}\in \mathbb {N} \ \forall n\geq n_{0}:c_{1}\cdot f(n)\geq g(n)\geq c_{2}\cdot f(n)\}}$

Oder etwas kompakter:

${\displaystyle \Theta (f(n))=O(f(n))\bigcap \Omega (f(n))}$

Anschaulich formuliert bedeutet das, dass ${\displaystyle \Theta }$ die Menge aller durch f nach unten und oben beschränkter Funktionen und somit die asymptotische untere und obere Schranke ist.

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))}$

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}$

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!!