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.
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.
$\displaystyle \forall f,g\in\mathcal{F}$: For any two functions $\displaystyle f$ and $\displaystyle g$ from the set $\displaystyle \mathcal{F}$,
$\displaystyle (f+g)\in\mathcal{O}(h)$: the fact that the function $\displaystyle (f+g)$ is in the set $\displaystyle \mathcal{O}(h)$
$\displaystyle \Rightarrow$: implies that
$\displaystyle f\in\mathcal{O}(h)$: $\displaystyle f$ is in the set $\displaystyle \mathcal{O}(h)$
$\displaystyle \land$: and
$\displaystyle g\in\mathcal{O}(h)$: $\displaystyle g$ is in the set $\displaystyle \mathcal{O}(h)$
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)?
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.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)?
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)".
Do you mean f * g rather than f + g? Then yes, that makes sense.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)?
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)?
Oh yes I meant f*g. Lol I think I was falling asleep when I wrote that.
Yes, provided it is obvious to you how to relate f(n) <= c*h(n) and $\displaystyle f\in\mathcal{O}(h)$ -- it is this fact that you need ultimately to show. (This is indeed obvious.)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)?