Wie beweise ich, dass das Beispiel in O(n^{1/3}) liegt?

Question

Aufgabe:

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

Problem/Ansatz:

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

=>  2^{\( n^{(1/2)} \)}   <=  c * 2 ^{\( 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)).

Answer 1

Aloha :)

Betrachte den Quotienten:

$$\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:$$\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)$$$$\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:$$\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: \(\quad 2^{\sqrt{\log n}}\in O\left(n^{1/3}\right)\)