Results 1 to 7 of 7
Like Tree4Thanks
  • 1 Post By romsek
  • 2 Post By Plato
  • 1 Post By romsek

Thread: Need help getting an intuitive idea of big-Omega notation

  1. #1
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Need help getting an intuitive idea of big-Omega notation

    Here is the definition I am going of of.
    Let
    f and g be real-valued functions defined on the same set of nonnegative real
    numbers. Then
    1.
    f is of order at least g, written f(x) is Big-Omega(g(x)), if, and only if, there exist a
    positive real number A and a nonnegative real number a such that A|g(x)| | f (x)| for all real numbers x > a.

    So I am wondering why the constant A is multipled by g(x). Is it basically saying, "hey, at a certain point, it doesnt matter what you multiply g(x) by, because f(x) is so big that its gonna always be bigger then the multiple of g(x)".
    Perhaps if someone could explain why x^2 is not Big-Omega(x) and that would help. I get how to solve problems it is jus the intuition I am missing.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,511
    Thanks
    2328

    Re: Need help getting an intuitive idea of big-Omega notation

    Quote Originally Posted by mdm508 View Post
    Here is the definition I am going of of.
    Let
    f and g be real-valued functions defined on the same set of nonnegative real
    numbers. Then
    1.
    f is of order at least g, written f(x) is Big-Omega(g(x)), if, and only if, there exist a
    positive real number A and a nonnegative real number a such that A|g(x)| | f (x)| for all real numbers x > a.
    I'm seeing the definition of $\mathcal{O}$ to be opposite what you've written

    in otherwords

    $f(x) \text{ is } \mathcal{O}(g(x)) \Leftrightarrow \exists A>0,~a>0 \ni |f(x)| \leq A |g(x)|,~x>a$

    this might help some

    https://www.cs.auckland.ac.nz/course...-lecture03.pdf
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: Need help getting an intuitive idea of big-Omega notation

    I am pretty sure the definition you provided is something else. I got that definition straight out of my book. Furthermore, the definition from the resource your provided is essentially the same as the one i provided.

    "The function g(n) is Ω(f(n)) iff there exists a
    positive real constant c and a positive integer n0
    such that g(n) ≥ cf(n) for all n > n0" Slide 1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,511
    Thanks
    2328

    Re: Need help getting an intuitive idea of big-Omega notation

    Quote Originally Posted by mdm508 View Post
    I am pretty sure the definition you provided is something else. I got that definition straight out of my book. Furthermore, the definition from the resource your provided is essentially the same as the one i provided.

    "The function g(n) is Ω(f(n)) iff there exists a
    positive real constant c and a positive integer n0
    such that g(n) ≥ cf(n) for all n > n0" Slide 1
    you've flipped the inequality sign

    it says $g(n) \text{ is }\mathcal{O}(f(n)) \Leftrightarrow g(n) \leq c f(n),~n > n_0$

    and you flipped it in your original post
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,511
    Thanks
    2328

    Re: Need help getting an intuitive idea of big-Omega notation

    Quote Originally Posted by romsek View Post
    you've flipped the inequality sign

    it says $g(n) \text{ is }\mathcal{O}(f(n)) \Leftrightarrow g(n) \leq c f(n),~n > n_0$

    and you flipped it in your original post
    to address your original question with the proper definition

    suppose $x^2 \sim \mathcal{O}(x)$

    Then $\exists A>0, a>0,~\ni x^2 \leq A x,~\forall x > a$

    $x^2 - A x \leq 0,~\forall x > a$

    $\left(x - \dfrac A 2\right)^2 - \dfrac {A^2}{4} \leq 0,~\forall x > a$

    $\left(x - \dfrac A 2\right)^2 \leq \dfrac {A^2}{4} \leq 0,~\forall x > a$

    the left side equals $\dfrac {A^2}{4}$ at $x = \dfrac{3A}{4}$ and increases as $x$ increases.

    So it should be clear that this expression is false $\forall x > \dfrac{3A}{4}$

    and thus $x^2 \text{ is not } \mathcal{O}(x)$
    Thanks from mdm508
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,866
    Thanks
    2513
    Awards
    1

    Re: Need help getting an intuitive idea of big-Omega notation

    Quote Originally Posted by romsek View Post
    you've flipped the inequality sign

    it says $g(n) \text{ is }\mathcal{O}(f(n)) \Leftrightarrow g(n) \leq c f(n),~n > n_0$

    and you flipped it in your original post
    It is not $\mathcal{O}$-notation it is $\Omega$-notation. See here.
    Thanks from romsek and mdm508
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,511
    Thanks
    2328

    Re: Need help getting an intuitive idea of big-Omega notation

    Quote Originally Posted by Plato View Post
    It is not $\mathcal{O}$-notation it is $\Omega$-notation. See here.
    Thanks.

    I'll be downstairs....

    in a pool of blood.
    Thanks from mdm508
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Oct 4th 2013, 11:11 AM
  2. Intuitive understanding of Frechet derivative?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Nov 21st 2011, 10:36 AM
  3. Replies: 3
    Last Post: Jul 25th 2011, 09:46 AM
  4. Intuitive order of definitions in arithmetic
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: Feb 14th 2011, 08:17 PM
  5. Counter-intuitive? or...
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Apr 3rd 2007, 08:43 PM

Search Tags


/mathhelpforum @mathhelpforum