Results 1 to 9 of 9

Thread: Growth of Functions

  1. #1
    Join Date
    Feb 2009
    Posts
    2,156
    Mentioned
    4 Post(s)
    Quoted
    42 Post(s)

    Default Growth of Functions

    Can someone go over proving if a function is Big O of another function and omega?

  2. #2
    Join Date
    May 2014
    Posts
    633
    Mentioned
    8 Post(s)
    Quoted
    321 Post(s)

    Default

    I guess one way to 'prove' a function f is Big O of another function g is to take lim(f/g) as n->infinity. If f = O(g) then this limit will come out to a constant. Also if this constant is 0, it also means f is in O(g) by definition since big O is meant to be *a* upper bound on the growth of a function.

    To prove omega, you should probably go about it with showing that if f is Omega(g) then f >= g for all n bigger than a certain N (sometimes it works for all n). Another way to check Omega is actually by the same method I gave in finding big O. However you want this limit to not be 0 this time as Omega is meant to be *a* lower bound on the growth of your function.

  3. #3
    Join Date
    Feb 2018
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    4 Post(s)

    Default

    Quote Originally Posted by JPHamlett View Post
    Can someone go over proving if a function is Big O of another function and omega?
    In order to do this you will need to use the definition and find both a c and a n0 s.t. 0<=f(n)<=cg(n) and n>n0
    That will prove f(n) is upper bounded by g(n) and that f(n) = O(g(n)).
    Omega is similar but you will need to use the definition for Omega and find c and n0 s.t. 0<=cg(n)<=f(n) and n>n0

  4. #4
    Join Date
    Feb 2018
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    4 Post(s)

    Default

    Quote Originally Posted by J_R View Post
    I guess one way to 'prove' a function f is Big O of another function g is to take lim(f/g) as n->infinity. If f = O(g) then this limit will come out to a constant. Also if this constant is 0, it also means f is in O(g) by definition since big O is meant to be *a* upper bound on the growth of a function.
    you may need to know L'hopitals rule for that. Just a heads up to the op

  5. #5
    Join Date
    May 2012
    Location
    Glorious Nippon
    Posts
    943
    Mentioned
    46 Post(s)
    Quoted
    476 Post(s)

    Default

    Quote Originally Posted by hunterofagoodtime View Post
    you may need to know L'hopitals rule for that. Just a heads up to the op
    I'm sure he is still struggling after almost 3 years.

  6. #6
    Join Date
    Dec 2006
    Location
    Program TEXAS home of AUTOERS
    Posts
    7,902
    Mentioned
    25 Post(s)
    Quoted
    225 Post(s)

    Default

    Quote Originally Posted by Citrus View Post
    I'm sure he is still struggling after almost 3 years.
    lolol


  7. #7
    Join Date
    Nov 2006
    Posts
    1,103
    Mentioned
    0 Post(s)
    Quoted
    6 Post(s)

    Default

    Quote Originally Posted by Citrus View Post
    I'm sure he is still struggling after almost 3 years.
    It's called a PhD....
    Infractions, reputation, reflection, the dark side of scripting, they are.

  8. #8
    Join Date
    Feb 2018
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    4 Post(s)

    Default

    ... I thought maybe someone would appreciate correctness on this website

  9. #9
    Join Date
    May 2018
    Location
    Toronto (Canada)
    Posts
    6
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    I'm also really bad at math and can't even slove first order equation. I'm actively looking for different programs, which provides an expert homework help.

    I can recommend you a writingcheap.com, very good assignment writing service.

    In my opinion, if you can't keep up with math and other subjects, just ask professionals for help.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •