1
$\begingroup$

I usually follow approach of taking logs and putting arbitrary large powers of $2$ for $n$ and reducing the given function to some constant value for large value of $n$. So in this case I did it as follows:

  • $\log{n}$

    Putting $n=2^{2^{2^{16}}}$ and taking $\log$

    $\log{\log(2^{2^{2^{16}}})}={2^{16}}$


  • $(\log{n})^c$

    Putting $n=2^{2^{2^{16}}}$, $c=2$ and taking $\log$

    $\log({(\log{2^{2^{2^{16}}}})^2})=\log({2\times(\log{2^{2^{2^{16}}}})})=\log({2\times(2^{2^{16}})})=\log{2}\times\log{2^{2^{16}}}$

    $=1+2^{16}$


  • $\sqrt{n}$

    Putting $n=2^{2^{2^{16}}}$ and taking $\log$

    $\log{\sqrt{2^{2^{2^{16}}}}}=\log{2^{2^{2^{{16}^{\frac{1}{2}}}}}}=\log{2^{2^{2^8}}}=2^{2^8}=2^{16}$

So it looks like:

$\log{n}=\sqrt{n}<(\log {n})^c$

However I checked that $\log{8}>\sqrt{8}$. But, $\log{(2^{2^{2^{16}}})}=64$, whereas $\sqrt{2^{2^{2^{16}}}}$ is much larger number making equality between the two unlikely.

  1. So where I am making mistakes in above calculations?
  2. How above three functions compare asymptotically?
$\endgroup$
  • $\begingroup$ Your approach simply isn't valid. You have just demonstrated it. $\endgroup$ – Yuval Filmus May 2 '16 at 16:11
  • $\begingroup$ In addition to your method not being valid (though it works fine as a heuristic I guess), you didn't apply it correctly. $\sqrt{2^{2^{2^{16}}}}$ is $2^{\left(\frac{1}{2} 2^{2^{16}}\right)}$, not $2^{2^{2^{\left(\frac{1}{2} 16\right)}}}$. $\endgroup$ – Craig Gidney May 2 '16 at 18:25
  • $\begingroup$ @CraigGidney are you sure ? is this wrong? $\endgroup$ – anir May 4 '16 at 19:29
  • $\begingroup$ @anir That calculator seems to be computing $((2^2)^2)^{16}$ instead of $2^{(2^{(2^{16})})}$. Conventionally, $2^{2^{2^{16}}}$ refers to $2^{(2^{(2^{16})})}$. If you intended $((2^2)^2)^{16}$, then the actual problem in your evaluation is that $\lg(((2^2)^2)^{16}) = 16 \lg((2^2)^2) = 64$, which is not the $(2^2)^{16}$ you assumed. $\endgroup$ – Craig Gidney May 4 '16 at 19:53
  • $\begingroup$ I feel I made huge mistakes above. Putting $n={2^{2^{2^{16}}}}$, $c=2$ & taking $log$, we get: (f1) $\log_2 n →\log_2 \log_2 {2^{2^{2^{16}}}}=2^{16}$ (f2) $(log_2 n)^c →\log_2 ((\log_2 {2^{2^{2^{16}}}})^2)=2×\log_2(\log_2(2^{2^{2^{16}}}))=2×2^{16}=2^{17}$ (f3) $\sqrt{n}→\log_2((2^{2^{2^{16}}})^{0.5})=0.5×\log_2(2^{2^{2^{16}}})=0.5×2^{2^{16}}=\frac{2^{65536}}{2}=2^{65535}$. So, $(f1)<(f2)<(f3)$ giving $f1=o(f2)$ & $(f2)=o(f_3)$. Can you please confirm if this is correct? $\endgroup$ – anir May 5 '16 at 19:52
1
$\begingroup$

for any $c>1,\epsilon>0$, $$\lim_{n\to\infty} \frac{(\log n)^c}{n^\epsilon} = 0$$

This means that $\log n=o( (\log n)^c)$ and $(\log n)^c = o(n^\epsilon)$. In particular, for $\epsilon =0.5$, $(\log n)^c = o(\sqrt{n})$.

See Reference answers to frequently asked questions

$\endgroup$

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