Komplexitätstheorie

[dot]

Oder eben z.B.

\begin{align*} n^{100} &< \epsilon \cdot 2^{\frac{n}{100}} \\ \Leftrightarrow\; \log\_2\left(n^{100}\right) &< \log\_2\left(\epsilon \cdot 2^{\frac{n}{100}}\right) \\ \Leftrightarrow\; 100 \cdot \log\_2(n) &< \log\_2(\epsilon) + \frac{n}{100} \\ \end{align*}

[Sone]

Das hatte ich schon längst.

[dot]

aber?

[Sone]

dot schrieb:

aber?

Wie hätte ich das gebrauchen können? n ist immer noch auf beiden Seiten der Ungleichung.
Durch den genialen Tipp mit L'Hospital habe ich n in einen Term gebracht.

[dot]

Aber der log(n) wird ab einem bestimmten n immer kleiner sein als n...

[Sone]

dot schrieb:

Aber der log(n) wird ab einem bestimmten n immer kleiner sein als n...

Oh! Stimmt. Ich bin halt dumm.

[Sone]

dot schrieb:

Aber der log(n) wird ab einem bestimmten n immer kleiner sein als n...

Ja, aber wie berechne ich n?

[Sone]

Hier ist die Ungleichung gelöst:

$n > log_2( \frac{100!}{(\frac{ln 2}{100})^{100}} ) * 100$

Einfach wunderschön.

[dot]

Wie kann das sein, dass deine Lösung unabhängig von $\epsilon$ ist?

[Sone]

dot schrieb:

Wie kann das sein, dass deine Lösung unabhängig von $\epsilon$ ist?

Verallgemeinere ich gerade.

[Sone]

Ja, die Lösung ist, einfach das Epsilon einfügen:

$n > log_2( \frac{100!}{\epsilon (\frac{ln 2}{100})^{100}} ) * 100$

Gut, das heißt, das hätte ich dann geschafft.