1. Proving big omega

Hi,

I'm hoping someone can help me solve the following question: $2^n - n^2 \in \Omega(2^n)$. I've been stuck on it for awhile now and really need some guidance.

Also the expansion of $2^n - n^2 \in \Omega(2^n)$ is $\exists c, n_0 \in \mathbb{R}^+, \forall n \in \mathbb{N}, n \geq n_0 \Rightarrow 2^n - n^2 \geq c \cdot 2^n$

I hope someone can help! And soon!!!

2. Re: Proving big omega

Try $c=\dfrac{1}{2}$. Now, you just need to find $n_0$ such that $2^{n_0-1}> n_0^2$. Try $n_0=10$. It should be clear that for any $n\ge n_0$, you have $2^n-n^2 \ge 2^n-2^{n-1} = \dfrac{1}{2}\cdot 2^n$.

3. Re: Proving big omega

can you please show the in-between steps of how $2^n - 2^{n-1} = \frac{1}{2} \cdot 2^n$?

4. Re: Proving big omega

Originally Posted by otownsend
can you please show the in-between steps of how $2^n - 2^{n-1} = \frac{1}{2} \cdot 2^n$?
There are no in between steps. $2^{n-1}$ means half of $2^n$. If you take away half of something, you are left with the other half.

5. Re: Proving big omega

Originally Posted by otownsend
can you please show the in-between steps of how $2^n - 2^{n-1} = \frac{1}{2} \cdot 2^n$?
Factor $2^n$ out of the left side. $2^n- 2^{n-1}= 2^n(1- 2^{-1})= 2^n\left(\frac{1}{2}\right)= \frac{1}{2}\cdot 2^n$.

6. Re: Proving big omega

oh jheez, exponents have never clicked for me. But that makes complete sense now. Thank you very much!