O-Notation / Landau-Notation: Beweis führen

Question

Aufgabe:

Welche der folgenden Aussagen sind korrekt?
Geben Sie einen Beweis an, um Ihre Antwort zu begründen.

(a)  3n² ∈ O(3ⁿ)

(b)  (9 ln n⁹)⁹ ∈ o(\( \frac{1}{9} \)\( \sqrt[9]{n} \))

Problem/Ansatz:

Folgende Definitionen habe ich gegeben:

O(f(n)) = {g(n) | ∃c>0, n₀>0. ∀n≥n₀. g(n) ≤ c * f(n)}

o(f(n)) = {g(n) | ∀c>0. ∃n₀>0. ∀n≥n₀. g(n) < c * f(n)}

zu (a):
Ich weiß, dass quadratische Funktionen langsamer wachsen als exponentielle. Da aber explizit nach einem Beweis verlangt wird, reicht dies noch nicht aus. Mein Ansatz:

3n² ≤ c * 3ⁿ          Sei c = 3, dann:

3n² ≤ 3 * 3ⁿ ⇔ n² ≤ 3ⁿ

Reicht es jetzt zu schreiben, dass quadratische Funktionen langsamer wachsen als exponentielle? Oder wie führe ich den Beweis weiter?

zu (b):
Hier habe ich absolut keine Idee, wie ich einen Beweis beginnen könnte.

!

Answer 1

Die Definition bei dir verlangt, dass es eine Konstante und eine Stelle n gibt, sodass ab dort die Abschätzung für alle n gilt. Das sieht sehr nach vollständige Induktion aus. Zu (a). Wähle zum Beispiel c=1 und n₀=3. Bei (b) kannst du dir mal beide Kurven plotten und eine Vermutung aufstellen, welches n du nehmen musst und führst dann wieder vollständige Induktion durch.