Informatiker Board | Druckvorschau: O-Notation die Dritte

Geschrieben von Shizmo am 15.03.2016 um 21:02:

O-Notation die Dritte

Hallo Wink

Zitat:

Gegeben sind zwei Funktionen $[latex]f_1,f_2: \mathbb{N} \to \mathbb{R^{+}}[/latex]$ , für die gilt $[latex]f_1 \in \mathcal{O}(g)[/latex]$ und $[latex]f_2 \in \mathcal{O}(g)[/latex]$ .
Beweisen oder widerlegen Sie folgende Aussagen:

$[latex]f_1 + f_2 \in \mathcal{O}(g)[/latex]$
$[latex]f_1 - f_2 \in \mathcal{O}(1)[/latex]$
$[latex]f_1 * f_2 \in \mathcal{O}(g^2)[/latex]$
$[latex]\frac{f_1}{f_2} \in \mathcal{O}(1)[/latex]$
$[latex]f_1 \in \mathcal{O}(f_2) \wedge f_2 \in \mathcal{O}(f_1)[/latex]$
$[latex]f_1 \in \mathcal{O}(f_2) \vee f_2 \in \mathcal{O}(f_1)[/latex]$

Ok, als erstes mal die Frage, was genau gemeint ist mit "beweisen", einfach nur zeigen oder wirklich mathematisch beweisen? Wie würde denn so ein Beweis denn ausschauen?

Also ich würde es so machen, weiß aber nicht ob man das so einfach machen darf:

$[latex]\mathcal{O}(g) + \mathcal{O}(g) = \mathcal{O}(g+g) = \mathcal{O}(g)[/latex]$ also richtig.
$[latex]\mathcal{O}(g) - \mathcal{O}(g) = \mathcal{O}(g-g) = \mathcal{O}(g)[/latex]$ also falsch.
$[latex]\mathcal{O}(g) * \mathcal{O}(g) = \mathcal{O}(g*g) = \mathcal{O}(g^2)[/latex]$ also richtig.
$[latex]\frac{\mathcal{O}(g)}{\mathcal{O}(g)} = \mathcal{O}(\frac{g}{g}) = \mathcal{O}(1)[/latex]$ also richtig.

Bei 5 und 6 kenn ich mich nicht ganz aus...

LG