Growth function and one misunderstanding point?!

Question

I have a question about Growth and Asymptotic notation topic.

My question is as follows:

$2^n$ > $n^{log_2{(n)}}$ is True.

anyone could say how we can deduce that this fact is true?

Answer 1

I assume you meant $\log_2(n)$ and not $\log_2^n$. If I'm right, then take logarithms, say in base 2 (just for convenience). On the left you have $n$. On the right you have $\log_2(n)^2$. Now use L'Hospital's rule to compute $\lim_{n \to \infty} \frac{n}{\log_2(n)^2}$. From the result of this and the fact that $2^x$ is an increasing function, you conclude that eventually $2^n$ is larger than $C n^{\log_2(n)}$ for any $C>0$.

If your question is about whether the statement is true for $C=1$ and any $n$ then that is another matter.

Answer 2

One way to solve these problems is visually. if we graph both solutions we see the $2^n$ (in orange) solution eventually outgrows $n^{nlog_2(n)}$ in blue.