algorithm - 证明函数加减法的大O

Question

假设f(n) = O(s(n))和g(n) = O(r(n))。证明或反驳（通过给出反例）以下主张：

1. f(n) - g(n) = O(s(n) - r(n))
2. 如果 f(n) = O(g(n))，则 f(n) + g(n) = O(s(n))

我真的不知道从哪里开始......请帮助一个年轻的学生。请给出解释，而不仅仅是解决方案。太感谢了。

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)