1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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}).$$

$\endgroup$
1
  • $\begingroup$ @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})$$ $\endgroup$
    – Jut
    Sep 3 '21 at 14:24
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I still cant get it. can you help more with the omega? $\endgroup$
    – violet
    Sep 3 '21 at 7:37
  • 1
    $\begingroup$ @violet, because $\sqrt{y}$ dominates $\log y$. $\endgroup$
    – zkutch
    Sep 3 '21 at 14:00
  • $\begingroup$ @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!? $\endgroup$
    – violet
    Sep 4 '21 at 2:46
  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Sep 4 '21 at 2:51
  • $\begingroup$ 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? $\endgroup$
    – violet
    Sep 4 '21 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.