Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
Problem Detail: 

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{n})^c$

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



  • $\sqrt{n}$

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


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?
Asked By : anir
Answered By : Ran G.

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

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback