0 Daumen
1,4k Aufrufe

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) \)

Avatar von

1 Antwort

0 Daumen

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).

Avatar von 1,5 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community