Is this proof correct? $2^\sqrt{2 \log n} \in Ω(\log^2n)$.

The goal is to prove: $2^\sqrt{2 \log n} \in Ω(\log^2n)$.

The author proves $f(n) \in Ω(g(n))$ by doing the following: first, the author shows that $log(f(n)) \in Θ(h(n))$. The author then shows $log(g(n)) \in Θ(t(n))$. By taking a limit, the author shows that $h(n)\in Ω(t(n))$. From this the authors concludes $f(n) \in Ω(g(n))$. But really, all the author has shown is this: $log(f(n)) \in Ω(log(g(n)))$, which certainly doesnt imply $f(n) \in Ω(g(n))$.

Do you agree with my thoughts on the author's proof/explanation of the problem statement?

$$$$$$$$

the proof: $$2^\sqrt{2\log n}=\sqrt[\sqrt{2\log n}]{n}.$$

Now after taking $\log$ from $=\sqrt[\sqrt{2\log n}]{n}$ and $\log^2n$, you get $$\log\left(\sqrt[\sqrt{2\log n}]{n}\right)=\Theta\left(\sqrt{\log n}\right).$$ Also $$\log\left(\log ^2n\right)=\Theta\left(\log\log n\right).$$ Since $$\lim_{n\to \infty}\frac{\sqrt{\log n}}{\log\log n}=\infty$$ So $$2^{\sqrt{2\log n}} \in \Omega(\log^2n).$$

credit of proof to Mohammad Rostami

Solution 1:

It seems you're using the convention $\log(a) = \log_2(a)$ and I'll also use this convention.

The proof you gave doesn't make sense to me so I'll write my own.

$$2^{\sqrt{2\log(n)}}\in \Omega(\log^2(n))\iff \log^2(n)\in O(2^{\sqrt{2\log(n)}})$$ That is $\log^2(n)/2^{\sqrt{2\log(n)}} = 2^{-\sqrt{2\log(n)}+2\log\log(n)}$ is bounded. That is, $-\sqrt{2\log(n)}+2\log\log(n)$ is bounded from above.

If we substitute $u = \sqrt{\log n}$ we get expression of the form $-c_1 u +c_2 \log(u)$ where $c_1, c_2$ are positive constants and $u\to \infty$. Since $-c_1 u +c_2 \log(u)\to -\infty$, it has to be bounded from above. In fact, we've even shown that $O$ can be replaced by $o$ so the relation $\Omega$ can be taken in the sense of Hardy-Littlewood as well.