# Thread: Prove/disprove these two claims

1. ## 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?

2. $\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)$

3. 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)?

4. 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?

5. Oops typo, I meant neither could be negative. ~

6. 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.

7. Originally Posted by emakarov
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)?
Originally Posted by emakarov
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.

8. 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.)