Which function grows faster

Question

Which function grows faster $f(n)=n^3$ or $g(n)=5^{\lg n}$ ?

Answer 1

Note that $g(n)=5^{\log_2 n}=2^{\log_2 n \cdot \log_2 5}=n^{\log_2 5}$. Since $\log_2 5>\frac 12$ you have that $g$ is "faster" than $f$ or, better, that $f\gg g$ as $n\rightarrow +\infty$, i.e. $\frac fg \rightarrow +\infty$ as $n\rightarrow +\infty$.

Answer 2

Attempt:

Set $2^a=5$, then $2 <a<3$ (Why?)

$5^{\lg_2 n} = 2^{a\lg_2 n}= 2^{\ lg_2 (n^a)}= n^a.$

Now compare $n^{1/2}$ with $n^a$.

Answer 3

Just write

• $5^{\log_2 n} = 2^{\log_2 5 \cdot \log_2 n} = n^{\log_2 5} > n^2 > n^{\frac{1}{2}}$

So, you have $$\frac{n^{\frac{1}{2}}}{5^{\log_2 n}} < \frac{n^{\frac{1}{2}}}{n^{2}} = \frac{1}{n^{\frac{3}{2}}} \stackrel{n \to \infty}{\longrightarrow} 0$$

which means that $5^{\log_2 n}$ grows faster than $n^{\frac{1}{2}}$ for $n \to \infty$.