Results 1 to 8 of 8

Math Help - Prove/disprove these two claims

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    33

    Prove/disprove these two claims

    I'm having trouble understanding this pair of claims:

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    \forall f,g\in\mathcal{F}: For any two functions f and g from the set \mathcal{F},

    (f+g)\in\mathcal{O}(h): the fact that the function (f+g) is in the set \mathcal{O}(h)

    \Rightarrow: implies that

    f\in\mathcal{O}(h): f is in the set \mathcal{O}(h)

    \land: and

    g\in\mathcal{O}(h): g is in the set \mathcal{O}(h)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    33
    Thanks for the explanation.
    So the first claim would be true right? If neither f nor g could be positive, then one of f or g must be smaller than f + g; and if f + g is smaller than c*h(n), then f/g is also smaller than c*h(n)?
    And the second would be false? Since either f or g could be greater than f + g if one of them is smaller than 1, then one of them could be greater than c*h(n)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    I agree that the answers are true for (1) and false for (2). However, your explanation makes no sense to me. First thing:
    If neither f nor g could be positive
    Why could they not be positive?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    33
    Oops typo, I meant neither could be negative. ~
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    So the first claim would be true right? If neither f nor g could be negative, then one of f or g must be smaller than f + g; and if f + g is smaller than c*h(n), then f/g is also smaller than c*h(n)?
    Ah, now I see. Another reason I was confused is f/g. This problem defines f + g as a function, so, by analogy, I thought that f/g is a function defined by (f/g)(x) = f(x) / g(x). I could not see how division fits the first problem.

    Finally, it would help to be consistent about the distinction between a function as a whole and its value at a particular point. Namely, in the phrase "f + g is smaller than c*h(n)", f + g is a function and c*h(n) is a number (and what is n)? At the risk of being pedantic, one could write, "if, for all n >= B, (f + g)(n) is smaller than c*h(n), then so are f(n) and g(n)".

    And the second would be false? Since either f or g could be greater than f + g if one of them is smaller than 1, then one of them could be greater than c*h(n)?
    Do you mean f * g rather than f + g? Then yes, that makes sense.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Feb 2010
    Posts
    33
    Quote Originally Posted by emakarov View Post
    Ah, now I see. Another reason I was confused is f/g. This problem defines f + g as a function, so, by analogy, I thought that f/g is a function defined by (f/g)(x) = f(x) / g(x). I could not see how division fits the first problem.

    Finally, it would help to be consistent about the distinction between a function as a whole and its value at a particular point. Namely, in the phrase "f + g is smaller than c*h(n)", f + g is a function and c*h(n) is a number (and what is n)? At the risk of being pedantic, one could write, "if, for all n >= B, (f + g)(n) is smaller than c*h(n), then so are f(n) and g(n)".
    Oh yes I meant "f or g" by the f/g. So basically for the proof all I need to write is something along the lines of "since (f+g)(n) <= c*h(n), and individually f(n) and g(n) <= (f+g)(n) since both could only be positive, then f(n) <= c*h(n) and g(n) <= c*h(n)?
    Quote Originally Posted by emakarov View Post
    Do you mean f * g rather than f + g? Then yes, that makes sense.
    Oh yes I meant f*g. Lol I think I was falling asleep when I wrote that.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    So basically for the proof all I need to write is something along the lines of "since (f+g)(n) <= c*h(n), and individually f(n) and g(n) <= (f+g)(n) since both could only be nonnegative, then f(n) <= c*h(n) and g(n) <= c*h(n)?
    Yes, provided it is obvious to you how to relate f(n) <= c*h(n) and f\in\mathcal{O}(h) -- it is this fact that you need ultimately to show. (This is indeed obvious.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prove or desprove claims
    Posted in the Calculus Forum
    Replies: 4
    Last Post: September 2nd 2011, 01:44 PM
  2. Prove or Disprove. Please help.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 3rd 2010, 03:37 AM
  3. Help me prove or disprove these claims
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 24th 2010, 10:45 AM
  4. Prove or Disprove
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 30th 2009, 08:47 AM
  5. how do u prove these claims?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 8th 2009, 11:59 AM

Search Tags


/mathhelpforum @mathhelpforum