Aufgabe:
Wir definieren die Quasiordnung \( \sqsubseteq \) auf Funktionen als \( f \sqsubseteq g \quad \) genau dann wenn \( f \in O(g) \).
Lösung:
\( \begin{array}{l} 0 \sqsubseteq 10^{400} \sqsubseteq 4 \sqsubseteq \log (n) \sqsubseteq n+10^{400} \sqsubseteq 1,01 n \sqsubseteq \log (n !) \sqsubseteq n \cdot \log \left(n^{3}\right) \\ \sqsubseteq n \cdot \log (n) \sqsubseteq n \cdot \sqrt{n} \sqsubseteq n^{2} \sqsubseteq n^{2} \cdot \log (n) \sqsubseteq \frac{n^{3}}{2} \sqsubseteq n^{3} \sqsubseteq 2^{n} \sqsubseteq n ! \sqsubseteq n^{n}\end{array} \)
Dabei können folgende Funktionen auch je in einer anderen Reihenfolge vorkommen, da diese je in der selben Komplexitätsklasse sind:
- \( 10^{400}, 4 \)
- \( 1,01 n, n+10^{400} \)
- \( \log (n !), n \cdot \log \left(n^{3}\right), n \cdot \log (n) \)
- \( \frac{n^{3}}{2}, n^{3} \)
man sollte die Funktionen hier jeweils nach der Quasiordnung ordnen.
Mein Problem ist jetzt wie folgt, wieso wächst log(n!) schneller als n + 10^400 und 1.01n, sollten nicht grundsätzlich Funktionen mit n^1 schneller wachsen als Funktionen ,die lediglich aus einem Logarithmus bestehen, und egal wie stark das Wachstum des Arguments im Logarithmus ist ?
