Landau Notation Frage?

Ich soll Aussagen ob (log n)^(log n) ∈ ω(2^((log n)^2))

Ich kriege das leider nicht hin. Ich versuche den Grenzwert zu bilden:

$\frac{\log\left(n\right)^{^{\log\left(n\right)}}}{2^{\log\left(n\right)^2}}=\left(\frac{\log\left(n\right)}{2^{\log\left(n\right)}}\right)^{^{\log\left(n\right)}}$ für n gegen unendlich.

Weiter komme ich nicht.

Wie bestimme ich den Grenzwert? Nur die Basis mit L'Hospital anschauen finde ich seltsam, genau so könnte man bei e = (1 + 1/n)^n argumentieren und behaupten e sei 1.

Answer 1

[Dogetastisch]

So, jetzt nochmal eine richtige Antwort.

Erstmal umformen:

$2^{\log\left(n\right)^2}=2^{\log\left(n\right)\cdot\log\left(n\right)}=n^{\log\left(n\right)}$ Dann bilden wir den Grenzwert von f(n)/g(n):

$\lim_{n\ to\ \inf}\ \left(\frac{\log\left(n\right)}{n}\right)^{\log\left(n\right)}$

Betrachten wir erstmal

$\lim_{n\ to\ \inf}\frac{\log\left(n\right)}{n}=\lim_{n\ to\ \inf}\frac{1}{n}\log\left(n\right)=\lim_{n\ to\ \inf\ }\log\left(\sqrt[n]{n}\right)=\log\left(\lim_{n\ to\ \inf}\ \sqrt[n]{n}\right)=\log\left(1\right)=0$

Wegen log(n) > 1 für n > 2 gilt, dass:

$0<\left(\frac{\log\left(n\right)}{n}\right)^{\log\left(n\right)}<\frac{\log\left(n\right)}{n}$ , folgt nach Sandwich-Theorem:

$\lim_{n\ to\ \inf\ }\left(\frac{\log\left(n\right)}{n}\right)^{\log\left(n\right)}=0$

, was zu zeigen war.

Woher ich das weiß: Studium / Ausbildung – Grundstudium Informatik (+ Mathematik)

Comments

[LandauFrage]

Danke :)

[Dogetastisch]

@LandauFrage

Gerne ^^
Ich seh nur gerade, dass du klein Omega meintest, nicht groß.

Das ist auf die Weise etwas kniffliger. Ich schau nochmal, was da geschickt wäre.

[LandauFrage]

@Dogetastisch

Nein, deine Lösung passt schon so. Sie sagt ja bereits aus, das (log n)^(log n) echt kleiner ist als n^(log n) von der Ordnung her. Also ist die Aussage mit klein Omega sowieso falsch.

[LandauFrage]

@LandauFrage

In der Musterlösung stand auch das hier klein o stehen muss

[Dogetastisch]

@LandauFrage

Ja gut, dass es vertauscht ist habe ich gar nicht gemerkt :D Habs unbewusst richtig interpretiert.

Aber das Problem bleibt, egal ob klein o oder klein Omega. Es muss für alle c für n groß genug gelten, dass f(n) > c*g(n), nicht nur für c=1.

[LandauFrage]

@Dogetastisch

Stimmt, insofern wäre der Grenzwert doch besser gewesen. Hmm.

[Dogetastisch]

@LandauFrage

Jo, habs mal auf die Weise verbessert. Ich denke das passt jetzt.

[LandauFrage]

@Dogetastisch

Sieht gut aus. Eig. ist die log n Information in der Frage des GW irrelevant gewesen. Hätte man genau so gut durch x ersetzen können.

Habe ich hier gemacht: https://www.gutefrage.net/frage/grenzwertberechnung-frage

Hab das parallel auch mal durchgerechnet, meine Lösung ist angehängt, vllt. findest du ja einen Fehler :D

[Dogetastisch]

@LandauFrage

Klar, man kann da auch das log(n) substituieren. Fragt sich, ob es dadurch einfacher wird. Ich vermute eher nicht.