Given $g(n) = O(f (n))$, how can I prove that the following expression is true:
$O(f (n) + g(n)) = O(f (n)) \tag1$
So I just write down what it says:
$g(n) = O(f (n)) <=> f(n) \le c_1 g(n) \text{ when } n\ge N_1 \tag2$
and
$h(n) = O(f(n) + g(n)) <=> f(n) + g(n) \le c_2 h(n) \text{ when } n\ge N_2 \tag3$
I am having trouble to find the next step. Can anyone help me finding the proof?
Hint: You can probably finish the proof yourself if you use the fact that $g(n)=O(f(n))$ means that there is a $c_1$ and $N_1$ such that $g(n)\le c_1f(n)$ if $n\ge N_1$. (You wrongly interchanged the roles of $f$ and $g$.)
Added: We have to prove two things, (i) $f(n)=O(f(n)+g(n))$ and (ii) $f(n)+g(n)=O(f(n))$.
In proving (i), there is basically nothing to do. In these calculations, we implicitly assume that $f(n)$, $g(n)$ are non-negative. Then $f(n)\le (1)(f(n)+g(n))$ for all $n\ge 1$. This proves that $f(n)=O(f(b)+g(n))$. The constant we use is $1$, and the inequality holds for all natural numbers.
Proving (ii) involves a little more work, and was the subject of the hint. Since $g(n)=O(f(n)$, there is a $c_1$ and $N_1$ such that $g(n)\le c_1f(n)$ for all $n\ge N_1$. It follows that $$f(n)+g(n)\le f(n)+c_1f(n)=(1+c_1)f(n)$$ for all $n\ge N_1$. This shows that $f(n)+g(n)=O(f(n)$.