These are simple to prove using the definition of the "O" thing:
- $f(n) = O(g(n))$ means that $\exists c, \exists N, \forall n > N, f(n) \le c g(n).$
So to prove the first theorem assume that:
- $\exists c_1, \exists N_1, \forall n > N_1, f(n) \le c_1 g(n).$
- $\exists c_2, \exists N_2, \forall n > N_2, z(n) \le c_2 h(n).$
and now we need to prove, using these:
- $\exists c_3, \exists N_3, \forall n > N_3, f(n) + z(n) \le c_3 (g(n) + h(n)).$
This is easy to do: Just let $c_3 = c_1 + c_2$ and $N_3 = N_1 + N_2$ then we must prove $\forall n > N_1 + N_2$:
- $f(n) + z(n) \le (c_1 + c_2) (g(n) + h(n))$
adding the two hypotheses we have together gives:
- $f(n) + z(n) \le c_1 g(n) + c_2 h(n)$
and clearly
- $c_1 g(n) + c_2 h(n) \le (c_1 + c_2) (g(n) + h(n))$
which gives the result.
As for part two, you just need to find some functions $f$ and $g$ such that you can prove $f(n) = O(g(n))$ and $\neg g(n) = O(f(n))$. $f(n) = n$ and $g(n) = n^2$ should do.