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:
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.
1 Antwort
![](https://images.gutefrage.net/media/user/x290914x/1619788897370_nmmslarge__72_29_505_505_ee103bcac26d4567cf830a04402dcc72.jpg?v=1619788897000)
So, jetzt nochmal eine richtige Antwort.
Erstmal umformen:
Dann bilden wir den Grenzwert von f(n)/g(n):
Betrachten wir erstmal
Wegen log(n) > 1 für n > 2 gilt, dass:
, folgt nach Sandwich-Theorem:
, was zu zeigen war.
![](https://images.gutefrage.net/media/user/x290914x/1619788897370_nmmslarge__72_29_505_505_ee103bcac26d4567cf830a04402dcc72.jpg?v=1619788897000)
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.
![](https://images.gutefrage.net/media/default/user/12_nmmslarge.png?v=1551279448000)
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.
![](https://images.gutefrage.net/media/default/user/12_nmmslarge.png?v=1551279448000)
In der Musterlösung stand auch das hier klein o stehen muss
![](https://images.gutefrage.net/media/user/x290914x/1619788897370_nmmslarge__72_29_505_505_ee103bcac26d4567cf830a04402dcc72.jpg?v=1619788897000)
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.
![](https://images.gutefrage.net/media/default/user/12_nmmslarge.png?v=1551279448000)
Stimmt, insofern wäre der Grenzwert doch besser gewesen. Hmm.
![](https://images.gutefrage.net/media/user/x290914x/1619788897370_nmmslarge__72_29_505_505_ee103bcac26d4567cf830a04402dcc72.jpg?v=1619788897000)
Jo, habs mal auf die Weise verbessert. Ich denke das passt jetzt.
![](https://images.gutefrage.net/media/default/user/12_nmmslarge.png?v=1551279448000)
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
![](https://images.gutefrage.net/media/user/x290914x/1619788897370_nmmslarge__72_29_505_505_ee103bcac26d4567cf830a04402dcc72.jpg?v=1619788897000)
Klar, man kann da auch das log(n) substituieren. Fragt sich, ob es dadurch einfacher wird. Ich vermute eher nicht.
Danke :)