Aufwandklasse in O - Notation. O-Klassen ordnen: O(n^5), O(n log n) und O(1).

Question

1. Beweisen Sie die folgenden Beziehungen:

b) \( \log n+n^{2}+n^{4} \in O\left(n^{5}\right) \)

c) \( 3 n \log n+7 n \in O(n \log n) \)

d) \( |\sin n| \in O(1) \)

f) \( 3^{n} \in 2^{O(n)} \)

2. Sortieren Sie die folgenden Aufwandsklassen bezüglich der Inklusionsrelation \( \subseteq \) :

\( O(\sqrt{n}), O\left(n^{3}\right), O\left(n^{2}\right), O(n \log n), O\left(2^{n}\right), O\left(n^{2} \log n\right), O(n), O(\log n), O(1) \)

Answer 1

d)  Es ist bekannt dass $$|\sin n| \leq 1$$

Also hat man dass $$|\sin n| \in O(1)$$

c)  $$n \leq n \log n, \forall n \geq 2$$

Also hat man dass n=O(n log n). Außerdem n logn=O(n logn).

Also hat man dass 3n logn+7n ∈ O(n logn).