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:
    cDMJw.jpg


    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