Beweis mit der O Notation

Question

Aufgabe:

Seien \(f, g :\space ℕ → ℕ\) monoton wachsende Funktionen. Beweisen Sie die folgenden Aussagen:

(1)  \(f(n) \in Ω(g(n)) ⇒ g(n) \in \mathcal{O}\Big((f(n))^4 \Big)\)

(2)  Sei \(h :\space ℕ → ℕ\) eine weitere monoton wachsende Funktion.

Zudem sei \(h(n) \in \mathcal{O}(f(n) +g(n))\) und \(g(n) \in \mathcal{O}(f(n))\).

Dann gilt auch \(h(n)\in \mathcal{O}(f(n))\).

Ist da jemand Fit bezüglich der \(\mathcal{O}\)-Notationen ?

Answer 1

Hallo :-)

Kennst du dazu folgende Definition?

Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). (in deiner Aufgabe ist der Wertebereich halt nur aus den natürlichen Zahlen, was aber egal ist)

$$\mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \text{ und } f(n)\leq \alpha\cdot g(n) }  \}. $$