Homework1.6a

gistfile1.txt

6) Let f1 and f2 be asymptotically positive functions. Prove or disprove each of the following conjectures. To disprove give a counter example. 
a. If f1(n) = O( g1(n)) and f2(n) = O( g2(n)) then f1(n)+f2(n) = O( g1(n)+g2(n) )
	Let f1(n) = O(g1(n)) and f2(n) = O(g2(n)) 
	This means that there must exist some constants c1 > 0 and c2 > 0 such
	That f1(n) ≤ c1g1(n) and f2(n) ≤ c2g2(n) for all n > 0.  
	We will find some constant, c3 that causes f1(n)+f2(n) ≤ c3 [g1(n) + g2(n)] for all
	n>0 integers:
    f1(n) + f2(n)≤ c1g1(n) + c2g2(n) 
                 ≤ max(c1, c2)g1(n) + max(c1, c2)g2(n) 
                 ≤ max(c1, c2) [g1(n) + g2(n)] 
                 = c3[g1(n) + g2(n)]

We found that c3 = max(c1, c2) which satisfies the definition of O notation, proving the claim: If f1(n) = O( g1(n)) and f2(n) = O( g2(n)) then f1(n)+f2(n) = O( g1(n)+g2(n) )