Frage/Bitte zur Genauigkeit bei der Klausur

[AnnaW]

Hallo,

ich hatte heute mein Testat. Da ich die Reihenfolge: \(e^{\log \log n^2} < \sqrt{\log n} < \log n^2\) hatte, meinte er, dass die Reihenfolge falsch sei. Die Begründung war, dass \(e^\log\) sich aufheben und aus \(e^{\log \log n^2}\) dann \(\log n^2\) wird. Das stimmt aber meiner Meinung nach nur, für \(e^{\ln}\). Wenn das in der Klausur so gedacht ist, könnte dann bitte eine Basis dabei stehen oder eben ganz klar \(\ln\)? Das würde das ganze dann eindeutiger machen.

Viele Grüße

Anna

[JannikV]

Du hast Recht, dass es angenehmer ist wenn da eine Basis bei steht.

Aber auch zu beliebiger Basis ist \(\sqrt{\log(n)} \in \mathcal{O}(e^{\log(\log(n^2))})\), da bei letzterem etwas im Exponenten wächst.

[AnnaW]

Wenn \(\log\) aber zur Basis 10 betrachtet wird, was ich generell getan habe, da wir keine Basis angegeben hatten kommt mit L'Hospital aber 0 heraus. Damit würde meine Reihenfolge wieder stimmen

[JannikV]

Das kann ich mir gerade nicht vorstellen
Wenns dir wichtig ist rechne es mir mal vor, dann gucke ich mal nach.

VG

[Schnell]

Du hast Recht, dass es angenehmer ist wenn da eine Basis bei steht.

Aber auch zu beliebiger Basis ist \(\sqrt{\log(n)} \in \mathcal{O}(e^{\log(\log(n^2))})\), da bei letzterem etwas im Exponenten wächst.

Hey, das dachte ich zunächst auch und hatte heut mein Testat, das ist aber wohl nicht so, denn:
e^log(log(n²)) kann man umformen zu log(n²)^log(e) und dann zu 2*log(n)^log(e), damit wäre es nur noch logarithmisch mit konstantem exponenten.
Edit: \(\sqrt{\log(n)} \in \mathcal{O}(e^{\log(\log(n^2))})\) würde dann nicht mehr stimmen wenn log(e)<0.5 ist, bei gegebener basis.

Außerdem steht in der Musterlösung wohl auch dass log(n)^(log(log(n))) langsamer wächst als sqrt(n), hier versteh ich aber nicht warum.
Wird es die Musterlösung irgendwann auch zum download geben? Das wäre hilfreich.

[AnnaW]

Ich hab das jetzt einfach mal in WolframAlpha eingegeben. Den Screenshot häng ich an ^^

[Schnell]

Ich hab das jetzt einfach mal in WolframAlpha eingegeben. Den Screenshot häng ich an ^^

Ja für die basis 10 stimmt das wohl auch, da log(e) dann 0,434 ist. Für den natürlichen logarithmus würde es dann nicht mehr gelten.
http://www.wolframalpha.com/input/?i=li ... Log.Log10-

[AnnaW]

Deswegen ja auch die Bitte, dass wir Basen angegeben bekommen, damit das eindeutig ist ^^

[JannikV]

Ok, dann hab ich mich wohl vertan..

[R_Egert]

Hallo,

wir betrachten das alles unter dem Punkt von asymptotischer Komplexität und dabei ist die Basis von den Logarithmen egal. Meiner Meinung nach müsste die vom Tutor genannte Umformung, bzw. die "Musterlösung" korrekt sein, da:

\(e^{\log_{10} \log_{10} n^2 } = e^{\frac{\ln (\log_{10} n^2)}{\ln 10}} = \frac{\log_{10} n^2}{\ln 10}\)

Da \(\ln 10\) eine Konstante ist, ist diese für die asymptotische Komplexität uninteressant. --> \(\log_{10} n^2\) ist korrekt und somit die Basis völlig egal.

Viele Grüße,

Rolf

[AnnaW]

Das ist aber nicht korrekt.

\(e^{\log_{10}(\log_{10}(n^2))} = e^{\frac{\ln(log_{10}(n^2))}{\ln(10)}}\) (jetzt darf man \(\frac{1}{\ln(10)}\) ausklammern) \(= (e^{\ln(\log_{10}(n^2))})^{\frac{1}{\ln(10)}}\) (da \(\ln(10) \approx 2.3\) gilt weiter) \(= \sqrt[2.3]{2*\log_{10}(n)}\), im Grenzwert gleich \(\sqrt[2.3]{\log_{10}(n)} < \sqrt{\log(n)}\). In der letzten Ungleichung ist die Basis des Logarithmus' asymptotisch irrelevant.


Im allgemeinen Fall ergibt sich also \(e^{\log_{a}(\log_{a}(n^2))} = \sqrt[\ln(a)]{\log_{a}(n)}\) was halt für \(\ln(a)>2\) asymptotisch kleiner als die Quadratwurzel des Logarithmus' ist, und für \(\ln(a)<2\) größer. Für \(\ln(a)=2\) sind sie identisch.

Viele Grüße

Anna

[Prof. Karsten Weihe]

Wenn das in der Klausur so gedacht ist, könnte dann bitte eine Basis dabei stehen oder eben ganz klar \(\ln\)? Das würde das ganze dann eindeutiger machen.

Klausuraufgaben sind sehr viel einfacher und nicht so "tricksig".

Grundsätzlich (zumindest bei mir): Sollte sich bei der Korrektur heraustellen, dass eine Aufgabe missverständlich war, wird jede plausible Interpretation des Aufgabentextes akzeptiert.

KW

[R_Egert]

Im allgemeinen Fall ergibt sich also \(e^{\log_{a}(\log_{a}(n^2))} = \sqrt[\ln(a)]{\log_{a}(n)}\) was halt für \(\ln(a)>2\) asymptotisch kleiner als die Quadratwurzel des Logarithmus' ist, und für \(\ln(a)<2\) größer. Für \(\ln(a)=2\) sind sie identisch.
Anna

Ah, stimmt. Ja hier hätte man das wohl wirklich genauer angeben sollen. Danke

Viele Grüße,

Rolf