Landau Symbole überprüfen

Question

Aufgabe:

Text erkannt:

Aufgabe 2 (12 Punkte).
(i) Seien $f, g: \mathbb{N}_{0} \rightarrow \mathbb{R}$ mit $f(n)=n^{2}$ und $g(n)=2^{n}$. Uberprüfen Sie, ob
(a) $f \in O(g)$,
(b) $f \in \Omega(g)$,
(c) $f \in \Theta(g)$,
(d) $f \in o(g)$,
(e) $f \in \omega(g)$
gelten. Begründen Sie Ihre Antworten.
(5P.)

Problem/Ansatz:

Ich habe paar Fragen zu der Aufgabe:

1. Ich habe aktuell gezeigt das klein o gilt, somit auch groß O. Ist das erstmal richtig?

2. Kann ich da klein o gilt direkt sagen, dass w als auch Ω nicht gelten kann? Das w nicht gilt kann auch ja auch mit f(x)/g(x) != ∞ zeigen, trotzdem die Frage. Könnte ich das umkehrt genauso erklären, wenn w gelten würde, also dass dann o und O nicht gelten können?

3. Was mache ich mit dem Θ?

Comments

Meine dritte Frage konnte ich mir glaube ich gerade selbst erklären, Θ gilt wenn O und Ω gelten, richtig?

Answer 1

Bei solchen Aufgaben hilft es immer wieder mal sich die Funktionen zeichnen zu lassen. Für die beiden Funktionen $f(n) = n²$ und $g(n) = 2^{n}$ sieht das so aus:

Jetzt müssen wir uns die Definitionen der einzelnen Symbole anschauen:

$f \in O(g)$ bedeutet, dass f unter g liegt.

$f \in Ω(g) ⇔ g \in O(f)$ ersteres bedeutet f liegt über g, das heißt automatisch, dass g unter f liegen muss.

$f \in Θ(g) ⇔f \in O(g) ∧ f \in Ω(g)$

$f \in o(g) ⇔ \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = 0$, das heißt g wächst schneller als f.

$f \in ω(g) ⇔ \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = \infty$, das heißt f wächst schneller als g.

Zur Lösung:

$f \in O(g)$ gilt schonmal, da ab ca. n = 4 die Funktion $f$ definitiv unter $g$ liegt.

$f \notin Ω(g)$ da f nur in einem kleinen Intervall ( $[2,3; 4)$) über g liegt, dann aber wieder darunter!

$f \in o(g)$ da g wesentlich schneller wächst als f. Dazu kann man sich einfach folgenden Grenzwert anschauen:

$\lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = \lim\limits_{n\to\infty} \frac{n²}{2^{n}} = 0$ da eine Exponentialfunktion immer schneller wächst als eine quadratische Funktion!

$f \notin Θ(g)$ da dafür $f \in O(g)$ und $f \in Ω(g)$ gelten müsste!

und $f \in ω(g)$ kann ebenfalls nicht gelten, da ja schon $f \in o(g)$ gilt. Das heißt wenn g schneller wächst als f, kann nicht auch f schneller als g wachsen. Das heißt $f \notin ω(g)$

PS: Ich weiß die Antwort kam spät, aber vielleicht hilft sie in Zukunft anderen Studierenden!

Comments

Die Definitionen sollte man wirklich genau anschauen. Auf wikipedia gibt es eine schöne Übersicht.

$f\in O(g)$ bedeutet, dass f unter g liegt.

$f\in \Omega(g)\iff g\in O(f)$ ersteres bedeutet f liegt über g, das heißt automatisch, dass g unter f liegen muss.

stimmt beides nicht.

---

Was sollte daran nicht stimmen?

---

Lies die Definition.

---

Ja, ich habe bei meiner Beschreibung ein wenig auf die mathematische Strenge verzichtet. Im Prinzip müsste ich oben noch hinzufügen, dass ab einem bestimmten $n_{0} \in \mathbb{N}$ für alle weiteren $n > n_{0}$ gilt dass $f(n)$ unter bzw. über $g(n)$ liegt. Wollte es aber diesbezüglich nicht zuuuu kompliziert erklären. Trotzdem danke für deine Anmerkung :)

---

Auch das stimmt nicht (etwas weniger falsch, aber weiterhin falsch). Hast Du die Definition nachgelesen, wo denn?

Answer 2

Deine Überlegungen sind alle völlig korrekt (auch die letzte Zusatzüberlegung).

Beachte aber, es gilt nicht $\cal O$, sondern es gilt $f\in {\cal O}(g)$. Die Kurzsprechweise ist anfällig, weil es ja manchmal auch um $g\in {\cal O}(f)$.

Alle diese Zusammenhänge findet man übersichtlich auf der Wikipedia-Seite.

Es ist auch sinnvoll, mit $f\in {\cal o}(g)$ anzufangen (Nachweis z.B. über l'Hospital). Dann folgt $f\in {\cal O}(g)$ sofort und man muss darüber nicht weiter nachdenken (mit drüber bzw. drunter liegen hat das nämlich nichts zu tun).