Warum wächst log(n!) schneller als 1.01n und n+10400

Question

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⁴⁰⁰ und 1.01n, sollten nicht grundsätzlich Funktionen mit n¹ schneller wachsen als Funktionen ,die lediglich aus einem Logarithmus bestehen, und egal wie stark das Wachstum des Arguments im Logarithmus ist ?

Comments

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 ?

Also sollte

log( exp( n⁵ ) ) = n⁵

grundsätzlich langsamer wachsen als n?

---

Nach der Stirling Formel ist

$$ n!∼\sqrt{2πn}(\frac{n}{e})^n $$

Also

$$ \log(n!)∼0.5\log(2πn)+n(\log(n)-1) $$

und n log(n) wächst schneller als n.

Answer 1

        \(\begin{aligned} 1,01n & =1,01+1,01\left(n-1\right) \end{aligned}\)

Im Falle von \(n\mapsto 1,01n\) wird der folgende Wert berechnet indem zum aktuellen Wert die konstante Zahl \(1,01\) addiert wird.

        \(\begin{aligned} \log\left(n!\right) & =\log\left(n\cdot \left(n-1\right)!\right)\\&=\log n+\log\left(\left(n-1\right)!\right) \end{aligned}\)

Im Falle von \(n\mapsto \log(n!)\) wird der folgende Wert berechnet indem zum aktuellen Wert der Wert \(\log n\) addiert wird. \(\log n\) kann beliebig groß sein.