Prove big O of addition and subtraction of functions

Question

Suppose f(n) = O(s(n)) and g(n) = O(r(n)). Prove or disprove (by giving a counter example) the following claims:

1. f(n) - g(n) = O(s(n) - r(n))
2. if f(n) = O(g(n)), then f(n) + g(n) = O(s(n))

I really have no idea where to even start.. please lend a hand to a young student. Please, give explanations and not just solutions. Thank you so much.

Answer 1

Formal definition : f(n)=O(s(n)) if and only if two constants M>0 and N>0 exist such as for all n>N , |f(n)|<M|g(n)|. (equivalent definitions exist such as the one given by adi, you can find more in wikipedia)

The two constants are not unique, but they cannot depend on the variable n, if they do there are not constant anymore and you will have proved nothing.

I strongly recommend you to calculate and to manipulate the definitions by yourself. Only reading answers will not be sufficient to cope with future problems involving the notions described here

a) is false : counter-example :

let f(n)=n, s(n)=n, g(n)=1 and r(n)=n

we have : f(n)=O(s(n)) (N=1, M=1 do the job for the definition) and g(n)=O(r(n)) (same, N=1, M=1)

let suppose that f(n)-g(n) = O(s(n)-r(n)), we have the two constants N, M verifying the definition :

for all n>N , |f(n)-g(n)|<M|s(n)-r(n)|

=> for all n>N , |n-1|<0

=> i won't go any further here, you can wisely choose a proper value for n which leads to a contradiction...

So s(n)-r(n) is not a Big-O of f(n)-g(n)

b) is false : counter-example :

let f(n)=1, s(n)=1 and g(n)=n

we have : f(n)=O(s(n)) (N=1, M=1 do the job for the definition) and f(n)=O(g(n)) (same, N=1, M=1)

let suppose that f(n)+g(n) = O(s(n)), we have the two constants N, M verifying the definition :

for all n>N , |f(n)+g(n)|<M|s(n)|

=> for all n>N , 1+n<M*1

=> here i choose to fix n for n=M+N (>N) , 1+M+N<M

=> for n=M+N (>N) , 1+N<0 which is impossible since N>0

So s(n) is not a Big-O of g(n)+f(n)