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{\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?
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 : http://cs.stackexchange.com/questions/56952

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback