1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Growth of Functions

  1. Mar 25, 2017 #1
    1. The problem statement, all variables and given/known data

    upload_2017-3-25_12-2-0.png

    upload_2017-3-25_12-2-59.png

    2. Relevant equations
    Provided in (1).

    3. The attempt at a solution
    I think (a) is no because, though ##c_1g > f,## the actual un-vertically-translated ##g## could be less than ##f,## meaning its lower bound ##c_2h < f## over ##c_2 \geq 1,## meaning ##h < f.## Am I correct on this?

    (b) I think the answer is yes. Am I correct in saying, if ##f## is ##O(g),## then ##g## is necessarily ##Ω(f)##? But I'm not sure how to prove it...
     
    Last edited: Mar 25, 2017
  2. jcsd
  3. Mar 25, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't understand your argument for (a).
    If the answer is "no", you can find an explicit counterexample. You don't have to provide it to solve the question, but that way you can be sure that you got it right.

    (b) while that is right, it is the opposite of what you want to show.
    The two equations given for the different cases look very similar, you can transform them into each other.
     
  4. Mar 25, 2017 #3
    Hi, thanks so much for replying! I'll try to explain my answer to (a) better. What I'm saying is:

    ##g## can be less than ##f## for ##\forall x \geq k,## in which case ##g##'s lower bound ##c_2h## must be less than ##f## for ##\forall x \geq k'.##
    If ##c_2h < f## then ##f > h## for ##c_2 \geq 1## so ##f## is not necessarily ##O(h).##

    For (b), I must admit I'm not sure where to begin w.r.t. transforming the equations into each other. We were not presented an example like this in class. Could you lend a bit more help here? Thanks so much again.
     
  5. Mar 25, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    But only in such a way that a constant can make it larger than f.
    f>h does not rule out f in O(h).

    Your approach won't work.
    You could test some functions to see if you find a counterexample.
    Can you write down the two relevant relations (one given, one to show) explicitly? You should note a very similar structure.
     
  6. Mar 25, 2017 #5
    I must be missing something, but why wouldn't ##\forall x > k ~~~ f(x) > h(x)## mean ##f \notin O(h)##?
    When I tried your suggested approach, this is what I got:

    I'm given ##\forall x \geq k_2 ~~~ c_2h(x) \leq g(x),## so by dividing by ##c_2## I arrive at ##\forall x \geq k_2 ~~~ h(x) \leq c_3g(x)## where ##c_3 = 1/c_2.##

    Is it that simple?
     
    Last edited: Mar 25, 2017
  7. Mar 25, 2017 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Because it could also be the case that f(x)<2h(x) for x>k.
    Yes. (I presume you are given c2>0.)
     
  8. Mar 25, 2017 #7
    Hi haruspex, thanks for replying.

    (a) What I meant to say was this:

    ##g## can be less than ##f.## Therefore, ##g##'s lower bound ##c_2h## must be less than ##f## over ##\forall x \geq k_2.## Therefore, with ##c = c_2## and ##k = k_2## as witnesses, it is not necessarily the case that ##f \in O(h).##

    Therefore, my answer to (a) is no. Is my answer correct?

    (b) So when the question asks for proof (values for witnesses), I would say the witnesses are ##c = c_3 = 1/c_2## and ##k = k_2,## correct?

    Thanks!
     
  9. Mar 25, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    "Can be" does not imply "must be". And you have to rule out the existence of any constant to show that f is not in O(h). It is not sufficient to give one constant where the inequality might be violated.

    Your approach won't work, no matter how long you try to fix holes.
    Looking for a counterexample is much easier.

    b: Right.
     
  10. Mar 25, 2017 #9
    I meant ##c_2h < f## when ##g < f## after ##x = k_2## (which is the point at which ##g > c_2h##). Sorry, I'm just trying to visualize the graphs in my head and think about the theory. I'm not sure how to come up with a counterexample...
     
  11. Mar 25, 2017 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    For a counterexample: g is "larger than" in both comparisons. Just pick something growing very fast, then find f and h.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Growth of Functions
  1. Exponential growth (Replies: 2)

  2. Function Growth Rates (Replies: 7)

  3. Population growth (Replies: 3)

  4. Plant Growth (Replies: 1)

Loading...