Prove/disprove these two claims

Feb 2010
21
0
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.
 

mathman

Forum Staff
May 2007
6,887
759
There seems to be something missing. What is O(h)?
 
Feb 2010
21
0
O(h) is defined by this, sorry left that out:

The definition of big Oh. f(n) has a slower growth rate than g(n).
 

mathman

Forum Staff
May 2007
6,887
759
The first one (sum) is true (note that both f and g are non-negative), since if either one grows faster than h, the sum will.

The second one (product) is false, since you can set either f or g = 0 and the other can grow at any rate.