0 Daumen
1,4k Aufrufe

Stellen Sie für die folgenden Paare von Funktionen jeweils fest, ob ƒ ∈ O(g), ƒ ∈ Ω(g) oder ƒ ∈ Θ(g) gilt. Wenn log ohne Basis angegeben wird, ist der Logarithmus zur Basis 2 gemeint.

Suchen Sie sich eine der Zeilen aus und beweisen Sie die Korrektheit Ihrer Antwort für diese Zeile rechnerisch.

Die anderen Zeilen dürfen Sie ohne Angabe des Lösungswegs ausfüllen.

\( f(n) \)\( g(n) \)\( f \in \mathcal{O}(g) \)\( f \in \Omega(g) \)\( f \in \Theta(g) \)
1\( \lfloor\sqrt{n}\rfloor \)\( 100 n \)
2\( \left\lfloor\log _{10}(n)\right\rfloor \)\( \left\lfloor\log _{2}(n)\right\rfloor \)
3\( \lfloor\sqrt[4]{n}\rfloor \)\( \lfloor\sqrt{n}\rfloor \)
4\( n^{3} \)\( \lfloor n \log (n)\rfloor \)
5\( 155 n^{2}+24 n+13 \)\( n^{2} \)
6\( \lfloor n \log (n)\rfloor+\lfloor\sqrt{n}\rfloor \)\( \left\lfloor n \log ^{3}(n)\right\rfloor \)
Avatar von
Du solltest erstmal hinschreiben was \( O(g) \), \( \Omega(g) \)  und \( \Theta(g) \) bedeuten.

Wie sind den O, Θ und Ω definiert?

Mit diesen Definitionen kannst du dann arbeiten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community