Question: I have to prove two equations and I can't understand them. Any help would be grateful because I have to consign the whole project in two days. 

These are the equations: 

1. If $f(n)=O(g(n))$ and $z(n)=O(h(n))$, then $f(n)+z(n)=O(g(n)+h(n))$.
2. I have to prove that this is wrong: $f(n)=O(g(n)) \Rightarrow g(n)=O(f(n))$.

Thanks in advance.

Answer: 
For the first question: For each big O, we know the existence of a constant $K$ and a number $N$. What happens if we take the larger of the two $K$s and the larger of the two $N$s?

For the second one, $1 = O(x)$.
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.