In welcher der folgenden Klassen liegt f?

Question

\( f_{1}(n):=2 \log n-2 n+n \log n \)
  In welcher der folgenden Klassen liegt \( \mathrm{f}_{1} \) ?
(Mindestens eine Antwort ist korrekt.)

\( O(n) \)
\( O(n \log n) \)
\( O\left(n^{2}\right) \)
In welcher der folgenden Klassen liegt \( f_{1} \) ?
\( \Omega(n) \)
\( \Omega(n \log n) \)
\( \Omega\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)

\( f_{2}(n):=\frac{3 n^{2}}{\log n} \)
In welcher der folgenden Klassen liegt \( f_{2} \) ?
\( O(n) \)
\( O(n \log n) \)
\( O\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)
In welcher der folgenden Klassen liegt \( \mathrm{f}_{2} \) ?
\( \Omega(n) \)
\( \Omega(n \log n) \)
\( \Omega\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)

\( f_{3}(n):=7 n-2^{20} \)
In welcher der folgenden Klassen liegt \( f_{3} \) ?
\( O(n) \)
\( O(n \log n) \)
\( O\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)
) In welcher der folgenden Klassen liegt \( f_{3} \) ?
\( \Omega(n) \)
\( \Omega(n \log n) \)
\( \Omega\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)

\( f_{4}(n):=\frac{4 n^{3}+7 n-4}{2 n+3} \)
In welcher der folgenden Klassen liegt \( f_{4} \) ?
\( O(n) \)
\( O(n \log n) \)
\( O\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)
In welcher der folgenden Klassen liegt \( f_{4} \) ?
\( \Omega(n) \)
\( \Omega(n \log n) \)
\( \Omega\left(n^{2}\right) \)
(Mindestens eine Antwort ist korrekt.)

Comments

Weißt du denn wie O und Ω definiert sind?

---

ja, f ∈ O(g) :⇔∃c ∈ R>0 : ∃n0 ∈ N>0 : ∀n ∈ N≥n0
:
0 ≤ f(n) ≤ cg(n

Seien f, g : N → R, dann gilt
f ∈ Ω(g) :⇔∃c ∈ R>0 : ∃n0 ∈ N>0 : ∀n ∈ N≥n0
:
0 ≤ cg(n) ≤ f(n)

Kannst du mir bitte nur die Lösungen nennen? Dann verstehe ich es besser

---

Kennst du auch die Charakterisierungen mit lim sup/lim inf bzw. dem Limes (Wenn der Grenzwert existiert sind lim sup und lim inf gleich dem Limes)?

https://de.wikipedia.org/wiki/Landau-Symbole

Z.B. beim ersten

f = 2 log(n) - 2n + n log(n)

g = n

Wenn du da

f/g = 2log(n)/n -2 +log(n)

betrachtest sieht du, dass dieser Bruch für n → ∞ gegen ∞ divergiert (erster Summand geht gegen 0, zweiter ist konstant, dritter geht gegen ∞).

Also gilt f ∉ O(n)

Dann betrachtest du g = n log(n)

f/g = 2/n - 2/log(n) + 1 → 1 < ∞ für n → ∞

Deshalb ist f ∈ O(n) und folglich auch direkt f ∈ O(n^2) (n^2 wächst asymptotisch schneller als n)

Dann zu den asymptotisch unteren Schranken:

f = 2 log n - 2n + n log n

g = n

f/g → ∞ > 0

Also f ∈ Ω(n)

g = n log(n)

f/g → 1 > 0

Hier auch f ∈ Ω(n log(n))

g = n^2

f/g → 0 das ist nicht echt größer als 0

Somit f ∉ Ω(n^2)

Und da du bei dieser Aufgabe immer Brüche rausbekommst die entweder konvergieren oder bestimmt divergieren ist es damit gar nicht schwer die Aufgabe zu lösen. Da du somit nur den Limes bestimmen musst und gar nicht lim sup und lim inf.

---

Vielen dank und wie ist es bei den anderen aufgaben

---

Gleiches Vorgehen.

---

Okay Dankeschön