I am having a hard time proving that $n^k$ is $O(2^n)$ for all $k$. I tried taking $\log_2$ of both sides and have $k\cdot \log_2 n =n$ but this is wrong. I am not sure how else I can prove this.
Thanks.
I am having a hard time proving that $n^k$ is $O(2^n)$ for all $k$. I tried taking $\log_2$ of both sides and have $k\cdot \log_2 n =n$ but this is wrong. I am not sure how else I can prove this.
Thanks.
Welcome to math.stackexchange!
When do we write $f(n) = O(g(n))$? When $\displaystyle\limsup_{n\to \infty} \frac{f(n)}{g(n)} < \infty $. So here, can you show $ \displaystyle \limsup_{n\to\infty} \frac{n^k}{2^n} < \infty$ ? I'm sure you can do much better than that! One approach you can try is a ratio test - show that eventually the terms decrease even quicker than some geometric sequence with ratio $<1$, which implies the limit here is $0$.
EDIT: Another method: $\displaystyle\frac{n^k}{2^n} < \frac{n^k}{e^n} $ and by power series, $\displaystyle e^n > \frac{n^{k+1} }{(k+1)!}$ so $ \displaystyle\lim_{n\to\infty} \frac{n^k}{2^n} \leq \lim_{n\to\infty} \frac{(k+1)!}{n} = 0$, which implies $ n^k = O(2^n)$ quickly in whatever definition you use.
Take $\lim_{n \to \infty}\frac{n^k}{2^n}$. The easiest thing is to take logs in both numerator and denominator and obtain $\frac{k}{\log 2}\lim_{n \to \infty}\frac{\log n}{n}$ then apply L'Hospital's rule and get 0, so the limit of the origianl ration is $e^0=1 < \infty$.