# Comparing asymptotic complexity of functions $\log{n}$, $(\log{n})^c$ and $\sqrt{n}$ [duplicate]

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?

## marked as duplicate by Raphael♦May 2 '16 at 18:44

• 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)}}}$. – Craig Gidney May 2 '16 at 18:25
• @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. – Craig Gidney May 4 '16 at 19:53
• 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? – anir May 5 '16 at 19:52
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})$.