How to prove that $n^k = O(2^n)$

Question

I'm having issues trying to prove this.

The Big Oh definition is: f(n) = O(g(n)) if exists a real constant $c > 0$ and $n_0 \in \Bbb N $ in such a way that for all $n \ge n_0$ we have f(n) $\le$ c.g(n)

In our case, $n^k \le c . 2^n$

Could you please help me?

Thanks in advance. :)

Answer 1

For nonnegative sequences $(f(n))$ and $(g(n))$, writing $f(n)=O(g(n))$ means there exists a real constant $c>0$ and $n_0\in\Bbb N$ such that for all $n\geq n_0$, $f(n)\leq c g(n)$, and that's all !

In your case, since $\displaystyle\lim_{n\to+\infty} \dfrac{n^k}{2^n}=0$, you know that $0<\dfrac{n^k}{2^n}\leq 1$ for $n$ sufficiently large, for example $n\geq n_0$, and so $0<n^k\leq 2^n$ for all such $n$. This matches the definition of $n^k=O(2^n)$, with $c=1$.