I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$

I want to show, without taking a limit, that $$2^\sqrt{2 \log n} \in Ω(\log^2n)$$ and $$2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$$.

I will omit what I have tried as it has not been useful.

Note that

$$2^\sqrt{2\log n}=2^{\frac{2\log n}{\sqrt{2\log n}}}$$$$=\left(2^{\log n}\right)^{\frac{1}{\sqrt{2\log n}}}$$

$$=n^{\frac{1}{\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).$$

For second problem, note that $$\sqrt{2}^{\log n}=\sqrt{n}.$$ So $$2^{\sqrt{2\log n}} =\mathcal{O}(\sqrt{2}^{\log n}).$$

• @integrator $$\log\left(\sqrt[\sqrt{2\log n}]{n}\right)=\log n^{\frac{1}{\sqrt{2\log n}}}=\frac{1}{\sqrt{2\log n}}\log n=\frac{1}{\sqrt{2}}\sqrt{\log n}=\Theta(\sqrt{\log n})$$
– Jut
Sep 3 '21 at 14:24

To prove $$2^{\sqrt{2\log n}} \in O(\sqrt{2}^{\log n})$$, you should note that $$\sqrt{2}^{\log n} = \left(\sqrt{2}^{\sqrt{\log n}}\right)^{\sqrt{\log n}}$$.

To prove $$2^{\sqrt{2\log n}} \in \Omega(\log^2n)$$, you should note that $$\log ^2n = 2^{2\log \log n}$$.

It will simplify the comparisons you have to do.

• I still cant get it. can you help more with the omega? Sep 3 '21 at 7:37
• @violet, because $\sqrt{y}$ dominates $\log y$. Sep 3 '21 at 14:00
• @zkutch I was thinking that taking exp of both sides of an inequality is not a valid step, but is the idea here that we can let c=1 and it is thereore a valid step!? Sep 4 '21 at 2:46
• For base>1 exp is increasing function, so $x>y \Leftrightarrow 2^x>2^y$. And, because, root vanish logarithm, we can take any constant. Sep 4 '21 at 2:51
• but in this case, what allows this method of proving to work is that we can let c=1 specifically. is this correct? because if we have cf(x)<g(x) and we do 2^cf(x)<2^g(x)- this may not be true in situations where c!=1? correct? Sep 4 '21 at 2:57