Results 1 to 6 of 6

Thread: Proving big omega

  1. #1
    Senior Member
    Joined
    Mar 2017
    From
    Massachusetts
    Posts
    329
    Thanks
    2

    Question 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!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,715
    Thanks
    1510

    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 $.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Mar 2017
    From
    Massachusetts
    Posts
    329
    Thanks
    2

    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$?
    Last edited by otownsend; Nov 2nd 2018 at 01:31 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,715
    Thanks
    1510

    Re: Proving big omega

    Quote Originally Posted by otownsend View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    20,032
    Thanks
    3160

    Re: Proving big omega

    Quote Originally Posted by otownsend View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Mar 2017
    From
    Massachusetts
    Posts
    329
    Thanks
    2

    Re: Proving big omega

    oh jheez, exponents have never clicked for me. But that makes complete sense now. Thank you very much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Big O and Omega help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 24th 2014, 05:46 PM
  2. Replies: 3
    Last Post: Jul 25th 2011, 10:46 AM
  3. Big Omega question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 20th 2009, 11:06 AM
  4. Big Oh and Big Omega
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 4th 2008, 01:01 AM
  5. Omega
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 20th 2008, 02:09 PM

/mathhelpforum @mathhelpforum