Wie sortiert man Funktionen nach asymptotischen Wachstum

Question

Aufgabe:

Wie sortiert man Funktionen nach asymptotischen Wachstum

Problem/Ansatz:

Gegeben seien Funktionen f1: 2^(nⁿ) f2: (2ⁿ)ⁿ f3: n^(2ⁿ) f4: (n²)ⁿ f5: (nⁿ) ².

Wie geht man da vor sowas asymptotisch aufsteigend zu sortieren? Sowas muss schnell im Kopf gehen aber ich hab kein Gefühl dafür... Weiß jemand wie man am besten vorgeht?

Answer 1

Eine sehr hilfreiche Regel für asymptotisches Ordnen ist

$n^k \prec a^n$ für $k\in \mathbb N$ und $a>1$

Damit ergibt sich schon mal:$$n^n \prec (n^2)^n = n^{2n} = (n^n)^2$$und$$(n^2)^n \prec (2^n)^n = 2^{n^2} \prec n^{2^n}$$ Außerdem folgt auch sofort$$2^{n^2} \prec 2^{n^n}$$Bleibt nur noch zu vergleichen

$n^{2^n} \stackrel{?}{\sim} 2^{n^n} \Leftrightarrow 2^n \ln n \stackrel{?}{\sim} n^n \ln 2$

Das erscheint mir für Kopfrechnen etwas sportlich. Es gilt

$\sqrt[n]{\frac{2^n\ln n}{n^n}} = \frac{2\ln^{\frac 1n}n}{n}\stackrel{n\to\infty}{\longrightarrow}0$

Daher ist $n^{2^n} \prec 2^{n^n}$.