The graphs of the two functions $f_1(n)=n^{\log{n}}$ and $f_2(n)=2^n$ clearly show that $f_2$ grows faster than $f_1$, but how do we mathematically prove this?
Asked
Active
Viewed 314 times
1 Answers
0
$n^{\log n} = e^{(\log n)^2}, 2^n = e^{n \log 2}$. Since $e^x$ is strictly increasing, it suffices to show that $n \log 2$ outgrows $(\log n)^2$. Using the limit $$ \lim_{n \to \infty} \frac{(\log n)^2}{n \log 2} = \frac{1}{\log 2} \left( \lim_{n \to \infty} \frac{\log n}{\sqrt n} \right)^2 = 0 $$ Hence $2^n = e^{n \log 2}$ grows faster than $n^{\log n} = e^{(\log n)^2}$.
Henricus V.
- 18,694
-
Could you please explain how n^(logn) = e^(logn)^2 and 2^n = e^(nlog2)? – acheigrec Apr 06 '16 at 01:00
-
@archeigrec Exponent laws. It is well known that $a^b = e^{b \log a}$. – Henricus V. Apr 06 '16 at 01:00