0 Daumen
243 Aufrufe

Aufgabe:

Beweise, dass 2log(n) \sqrt{log(n)}  ∈ O(n(1/3) )


Problem/Ansatz:

=>  log(2n(1/2) n^{(1/2)} ) <= c * n(1/3) 

=>  2n(1/2) n^{(1/2)}   <=  c * 2 n(1/3) n^{(1/3)}

Ist die Umformung von Wurzeln log(n) im Exponent soweit richtig oder warum komme nicht zur Komplexitätsklasse O(n (1/3)).

Avatar von

1 Antwort

+1 Daumen

Aloha :)

Betrachte den Quotienten:

2lognn1/3=2logn2log(n1/3)=2logn213logn=2logn13logn\frac{2^{\sqrt{\log n}}}{n^{1/3}}=\frac{2^{\sqrt{\log n}}}{2^{\log\left(n^{1/3}\right)}}=\frac{2^{\sqrt{\log n}}}{2^{\frac13\log n}}=2^{\sqrt{\log n}-\frac13\log n}

Der Exponent sieht so schlimm aus, wie er ist. Wir formen ihn wie folgt um:logn13logn=13(logn3logn)=13(logn3logn+9494)\sqrt{\log n}-\frac13\log n=-\frac13\left(\log n-3\sqrt{\log n}\right)=-\frac13\left(\log n-3\sqrt{\log n}+\frac94-\frac94\right)logn13logn=13(logn3logn+94)+912=13(log(n)32)2+34\phantom{\sqrt{\log n}-\frac13\log n}=-\frac13\left(\log n-3\sqrt{\log n}+\frac94\right)+\frac{9}{12}=-\frac13\left(\sqrt{\log(n)}-\frac32\right)^2+\frac{3}{4}

Damit können wir den Grenzwert unseres Quotienten von oben bestimmen:limn(2lognn1/3)=limn213(log(n)32)2+34=234limn1213(log(n)32)2=2340=0<\lim\limits_{n\to\infty}\left(\frac{2^{\sqrt{\log n}}}{n^{1/3}}\right)=\lim\limits_{n\to\infty}2^{-\frac13\left(\sqrt{\log(n)}-\frac32\right)^2+\frac{3}{4}}=2^{\frac34}\cdot\lim\limits_{n\to\infty}\frac{1}{2^{\frac13\left(\sqrt{\log(n)}-\frac32\right)^2}}=2^{\frac34}\cdot0=0<\infty

Daher gilt: 2lognO(n1/3)\quad 2^{\sqrt{\log n}}\in O\left(n^{1/3}\right)

Avatar von 152 k 🚀

Ein anderes Problem?

Stell deine Frage