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