1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Prove/disprove these two claims

  1. Mar 20, 2010 #1
    1. The problem statement, all variables and given/known data
    I'm having trouble understanding this pair of claims:

    2. Relevant equations

    3. The attempt at a solution

    So g is some function whose result is greater or equal to 0... but I don't really get what the rest of the claim means.
    Could someone please explain them to me?
    Thanks in advance.
  2. jcsd
  3. Mar 20, 2010 #2
    [tex]\mbox{ If } f(n)= O(g(n)), \mbox{ then it means that the function f(n) is of order at most g(n)}.[/tex]

    [tex]\mbox{ That is, by def., f(n) is big oh of g(n) if ther exists some positive constant C such that}[/tex]

    [tex]|f(n)|\leq C|g(n)|[/tex]

    Considering this, then what the problem is asking is that if f+g is of order at most h, then each of f and g must be of order at most h.

    I haven't worked any of these problems out myself, but a proof by contradiction looks promising.
  4. Mar 21, 2010 #3
    Ok thanks for clearing it up.
    So basically it's saying:
    If f(n) + g(n) [tex]\leq[/tex] c[h(n)]
    Then f(n) [tex]\leq[/tex] c[h(n)] and g(n) [tex]\leq[/tex] c[h(n)]
    The tricky part is that f(n) could be negative right? Since it says "[tex]\forall[/tex] f". Then f(n) could be larger than (f + g)(n)? Or does "[tex]\forall[/tex] f, g [tex]\in[/tex] F" mean "for all f and g that are in F"?
    Last edited: Mar 21, 2010
  5. Mar 21, 2010 #4
    Look at the definition of f:N-->R+. Yes ti means for all f, g that are in F.
  6. Mar 21, 2010 #5
    Oh ok, then the answer would be obvious right? I mean if both f and g has to be positive, then either f or g has to be smaller than f + g; then they have to be in O(h) as well.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook