Laufzeit-Notationen

Funktionen die asymptotisch nicht schneller als g wachsen

\{f: \mathbb{N} \rightarrow \mathbb{R} \; | \; \textcolor{yellow}{\exists} c \in \mathbb{R}_{+} : \exists n_{0} \in \mathbb{N} : \forall n \geq n_{0} : f(n) \textcolor{yellow}{\leq} c \cdot g(n)\}$$ > Funktionen die asymptotisch **nicht langsamer** als g wachsen $$\mathcal{\Omega}(g) := \{f: \mathbb{N} \rightarrow \mathbb{R} \; | \; \textcolor{yellow}{\exists} c \in \mathbb{R}_{+} : \exists n_{0} \in \mathbb{N} : \forall n \geq n_{0} : f(n) \textcolor{yellow}{\geq} c \cdot g(n)\}$$ > Funktionen die asymptotisch das **gleiche** Wachstum wie g haben $$\mathcal{\Theta}(g) := \mathcal{O}(g) \cap \mathcal{\Omega}(g)$$ > Funktionen die asymptotisch **langsamer** als g wachsen $$\mathcal{o}(g) := \mathcal{O}(g) \backslash \mathcal{\Omega}(g)$$ $$\Rightarrow \{f: \mathbb{N} \rightarrow \mathbb{R} \; | \; \textcolor{yellow}{\forall} c \in \mathbb{R}_{+} : \exists n_{0} \in \mathbb{N} : \forall n \geq n_{0} : f(n) \textcolor{yellow}{\leq} c \cdot g(n)\}$$ > Funktionen die asymptotisch **schneller** als g wachsen $$\mathcal{\omega}(g) := \mathcal{O}(g) \backslash \mathcal{\Omega}(g)$$ $$\Rightarrow \{f: \mathbb{N} \rightarrow \mathbb{R} \; | \; \textcolor{yellow}{\forall} c \in \mathbb{R}_{+} : \exists n_{0} \in \mathbb{N} : \forall n \geq n_{0} : f(n) \textcolor{yellow}{\geq} c \cdot g(n)\}$$ [[Laufzeit]]