Zunächst eine theoretische Frage: Gibt es da irgendwelche Vorschriften/Empfehlungen o.ä., wann man per Ungleichung …

Question

Aufgabe:

Schönen guten Tag, folgende Aufgabe bereitet mir gerade Probleme:

Beweisen Sie die folgenden Aussagen:

i) log(n²)  ∈  O(log n)

ii) 50n² + 30  ∈  Θ(n²)

iii) n·log n ∈ Ω(n)

Dies muss jeweils mit einer der folgenden Definitionen bewiesen werden:

O(n): Es existieren zwei Konstanten c ∈ ℝ+ und n0 ∈ ℕ, sodass für alle n ≥ n0 die Ungleichung 0 ≤ f(n) ≤ c · g(n) gilt.

Θ(n): Es existieren 3 Konstanten c1, c2 ∈ ℝ+ und n0 ∈ ℕ, sodass für alle n ≥ n0 Ungleichung 0 ≤ c1 · g(n) ≤ f(n) ≤ c2 · g(n) gilt.

Ω(n): Es existieren zwei Konstanten c ∈ ℝ+ und n0 ∈ ℕ, sodass für alle n ≥ n0 die Ungleichung 0 ≤ c · g(n) ≤ f(n) gilt.

Alternativ kann man das Ganze natürlich auch mithilfe des Grenzwerts berechnen. Zunächst eine theoretische Frage: Gibt es da irgendwelche Vorschriften/Empfehlungen o.ä., wann man per Ungleichung vorgehen sollte und wann per Grenzwert?

Im Weiteren wäre ich sehr dankbar, wenn mir jemand die Beweise ausführlich zeigen würde, sodass ich auch sicher dahinter komme und das allgemeine Vorgehen und Beweisen bei diesen Aufgaben verstehe.

Mit freundlichen Grüßen und besten Dank

JP

Answer 1

Aloha :)$$f(n)\in O(g(n))\quad\Longleftrightarrow\quad\lim\limits_{n\to\infty}\operatorname{sup}\left|\frac{f(n)}{g(n)}\right|<\infty\quad\text{(obere Schranke)}$$$$f(n)\in \Omega(g(n))\quad\Longleftrightarrow\quad\lim\limits_{n\to\infty}\operatorname{inf}\left|\frac{f(n)}{g(n)}\right|>0\quad\text{(untere Schranke)}$$$$f(n)\in\Theta(g(n))\quad\Longleftrightarrow\quad f(n)\in O(g(n))\;\land f(n)\in \Omega(g(n))$$

Answer 2

Fang mal mit (i) an, wende ein log-Gesetz an und Du kannst die Konstante c direkt ablesen. Es ist immer gut, mit einem Erfolgserlebnis zu starten. Auch das n0 ist nicht schwer zu erkennen.

Beachte, in Deiner Def. von O(...) muss links \(f(n)\in O(g(n))\) stehen, nicht nur \(O(n)\), genauso bei den anderen Landau-Symbolen. Was ist dann bei (i) \(f(n)\) und \(g(n)\)?