Lösen von Ungleichungen für Asymptotische Ordnungen

Question

Hallo erstmal!

Ich habe zur Zeit mit der Berechnung der asymptotischen Ordnung zu kämpfen. Eigentlich mehr ein Problem der Informatik, aber in diesem Fall sortiere ich es lieber hier ein, als in der Stacklounge, da die Fragestellung bzw. meine Probleme eher mathematischer Natur sind. Sollte dies doch ein Problem sein, bitte einen Hinweis geben, dann eröffne ich das ganze dort neu.

Aufgabe:

Beweis anhand der Definition der asymptotischen Ordnung:

$$ O(f) = {T | T: \mathbb{N}\rightarrow \mathbb{R}_{0}^{+} \; \text{und} \; \exists c \in R^{+} \exists n_{0} \in \mathbb{N} \; \forall n \geq n_{0}: T(n) \leq c*f(n)}$$

Es soll bewiesen werden für:

$$n^2+2n+3 \in O(n^2)$$

$$log(n) \in O(n)$$

$$2^{n+a} \in O(3^n)$$

Problem/Ansatz:

Nachdem ich nach langer Zeit erstmal wieder ins Rechnen kommen musste, habe ich zumindest für die erste Ungleichung eine Lösung gefunden.

$$ n^2+2n+3 \leq 2n^2$$

hat ja durch Lösen der Quadratischen Funktion die Lösung $$3 \leq n$$

So ergeben sich weitere Ungleichungen:

$$log(n) \leq c*n$$

$$2^{n+a} \leq c*3^n$$

Leider habe ich für die folgenden Teile keine guten Ansätze. Höchstens bei der letzten Teilaufgabe, das man über die Potenzgesetze gehen könnte, die Exponenten aufteilt und dann 2^a als Konstante nimmt.

Answer 1

n²+2n+3≤2n²

Hat die Lösungsmenge {n|(3-√17)/2≤n≤(3+√17)/2}

Comments

n^2+2n+3≤2n^2    hat die Lösungsmenge {n|-1≤n≤3}

Aha.

---

Danke für die Antwort, da c aber in R⁺ sein soll, ist das für diese Aufgabe keine mögliche Lösung. Alternativ geht ja auch c=6 n₀=1

---

n²+2n+3≤2n²    hat die Lösungsmenge {n|-1≤n≤3}
nach kommentarloser Korrektur:Lösungsmenge {n|(3-√17)/2≤n≤(3+√17)/2}

Die Ungleichung  n² + 2n + 3 ≤ 2n²  hat über ℝ die

 Lösungsmenge  L = ] -∞ ; -1 ] ∪ [ 3 ; ∞ [

Bezogen auf n∈ℕ [ n∈ℝ⁺]  also n ≥ 3 (wie im Fragetext angegeben)