Asymptotic Notation Properties. Let

f(n)

and

g(n)

be asymptotically non-negative functions. Using the definitions of asymptotic notations:\ (a) (4 points) Prove that if

f_(1)(n)=O(g_(1)(n))

and

f_(2)(n)=O(g_(2)(n))

then

f_(1)(n)+f_(2)(n)=O(g_(1)(n)+g_(2)(n))

\ (b) (4 points) Prove that if

f(n)=O(n)+O(n^(2))+O(n^(3))

then

f(n)=O(n^(3))

.\ 3

3. Asymptotic Notation Properties. Let f(n) and g(n) be asymptotically non-negative functions. Using the definitions of asymptotic notations: (a) (4 points) Prove that if f1(n)=O(g1(n)) and f2(n)=O(g2(n)) then f1(n)+f2(n)=O(g1(n)+g2(n)). (b) (4 points) Prove that if f(n)=O(n)+O(n2)+O(n3) then f(n)=O(n3)