Groß-O-Notation - cosinus und Beschränktheit

Question

Hallo, ich verstehe folgende Musterlösung zu meinem Übungsblatt nicht:

Text erkannt:

- Die Behauptung \( 5 \cos (n)+n=\mathrm{O}(1) \) gilt nicht: \( 5 \cos (n) \leq 5 \forall n \in \mathbb{N} \), womit gilt \( 5 \cos (n)= \) \( \mathrm{O}(1) \), jedoch ist der zweite Teil nicht beschränkt und somit der Ausdruck insgesamt nicht in \( \mathrm{O}(1) \).

1. Wieso setzt man 5 für g(n) ein? Und wo ist "+ n" in f(n) hin?

2. Ich habe mir nochmal die Definition und Darstellung bezüglich der Beschränktheit angesehen, doch wieso ist das hier ein Problem? Weil es nicht beliebig große n geben kann (was gegen die Def. der Groß-O-Notation verstößt) ?

Answer 1

\( 5 \cos (n) \leq 5 \forall n \in \mathbb{N} \),

Verstehst du diese Aussage?

womit gilt \( 5 \cos (n)= \) \( \mathrm{O}(1) \)

Verstehst du, warum diese Aussage aus obiger Aussage folgt?

jedoch ist der zweite Teil nicht beschränkt

Mit dem zweiten Teil ist der Summand \(n\) in dem Ausdruck \(5\cos(n) + n\) gemeint. Verstehst du, warum der Summand nicht beschränkt ist?

und somit der Ausdruck insgesamt nicht in \( \mathrm{O}(1) \).

Mit dem Ausdruck ist \(5\cos(n) + n\) gemeint.

Verstehst du, warum aus der Tatsache, dass \(5\cos(n) = O(1)\) ist und dass \(n\) nicht beschränkt ist, die Tatsache folgt, dass \(5\cos(n) + n\) nicht \(O(1)\) ist?

Wieso setzt man 5 für g(n) ein?

Was ist \(g(n)\)?

Und wo ist "+ n" in f(n) hin?

Was ist \(f(n)\)?

Beschränktheit angesehen, doch wieso ist das hier ein Problem?

Eine nicht beschränkte Funktion kann nicht \(O(1)\) sein.

Weil es nicht beliebig große n geben kann

Es kann beliebig große \(n\) geben. Falls du anderer Meinung bist, dann gib eine obere Schranke an.

Comments

Danke für die Antwort!!

Verstehst du diese Aussage?

Verstehst du, warum diese Aussage aus obiger Aussage folgt?

Verstehst du diese Aussage?

Ich verstehe leider nicht, wie man auf die Ungleichung kommt...bzw. warum hier ausgerechnet 5 auf der rechten Seite der Ungleichung eingesetzt wurde.

Verstehst du, warum diese Aussage aus obiger Aussage folgt?

Ja, da 5 in O(1) liegt und 5 cos (n) kleiner gleich 5 ist, kann es auch nur in O(1) liegen.

Verstehst du, warum der Summand nicht beschränkt ist?

Weil n in der Menge der natürlichen Zahlen liegt die unendlich ist?

Also ich würde sagen, dass der Gesamtausdruck in O(n) liegt, weil wenn 5 cos(n) alleine betrachtet in O(1) ist dann fällt die 1 weg, weil sie eine Konstante ist und n bleibt, da komplexer?

Ach zu g(n) und f(n): Die kommen aus der Definition, hatte vergessen die hier zu posten...