Welche Funktion wächst schneller?

Question

Aufgabe:

Welche Funktion wächst schneller?

f(n)=log(n!)

g(n)=n^(log(n))

Problem/Ansatz:

log(n!)=2^(log(log(n!)) > 2^(log(n))

n^(log(n))=2^(log(n^(log(n))=2^(log(n)^2)

würde sagen g(n) wächst schneller, bin mir da aber nicht sicher

Answer 1

Hallo :-)

Deine Rechnungen sind zunächst in sich richtig, aber für deine Behauptung nicht zielführend.

Ich biete folgenden Ansatz an:

$$ f(n)=\ln(n!)=\sum\limits_{k=1}^n \ln(k)\leq \sum\limits_{k=1}^n\ln(n)=n\cdot \ln(n)\leq n^2\stackrel{n\geq 8}{\leq}n^{\ln(n)}=g(n) $$

Answer 2

Deine Abschätzung ist zwar korrekt, hilft dir aber hier nicht wirklich weiter (du schätzt die eine Funktion ja von unten ab, damit kannst du aber hier nicht zeigen, das sie langsamer als die andere wächst). Hier mal eine Möglichkeit: Es ist klar, dass

\(\begin{aligned} \log _{2}(n !) \leq \log _{2}\left(n^{n}\right)=n \log _{2}(n)\end{aligned} \)
gilt. Nun können wir zeigen, dass \( n^{\log _{2}(n)} \) sogar schneller als diese obere Abschätzung wächst, z.B. unter Betrachtung des folgenden Grenzwertes (zur Einfachheit werde ich den natürlichen Logarithmus verwenden, dieser unterscheidet sich ja nur um einen Konstanten Faktor von jedem andern Logarithmus)
\(\begin{aligned} \lim \limits_{n \rightarrow \infty} \frac{n^{\ln (n)}}{n \ln (n)} \stackrel{\text { l'Hopital }}{=} \lim \limits_{n \rightarrow \infty} \frac{2 \dfrac{n^{\ln (n)} \ln (n)}{n}}{\ln (n)+1}=\infty\end{aligned} \)