1

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. :)

Reslley Gabriel
  • 89
  • 2
  • 8

1 Answers1

2

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$.

Philippe Malot
  • 2,667
  • Thanks. But how can we prove that the limit tends to zero? Don't I need to specify the value of $n_0$? – Reslley Gabriel Apr 20 '13 at 23:53
  • Writing $\dfrac{n^k}{2^n}=\dfrac{e^{k\ln n}}{e^{n\ln 2}}=e^{k\ln n-n\ln 2}=e^{n\left(\frac{\ln n}{n}-ln 2\right)}$ should help you to find the limit. And no, you don't need to specify the value of $n_0$, you just need know that such a number exists by the definition of the limit (I took $\varepsilon=1$ in the usual definition). – Philippe Malot Apr 21 '13 at 00:20