# Two questions in asymptotic notation

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))$.

-
It is not even close to rude to ask us to hurry up. It is much worse. –  Asaf Karagila Nov 25 '11 at 23:21
Where does it say "hurry up"? –  user16697 Nov 25 '11 at 23:31
@QED If 7 people upvote a comment, it is fair to assume that they did not hallucinate the event. Most likely it was a comment by the OP that got deleted later. –  Phira Nov 26 '11 at 12:15
@Phira, "if lots of people say something then it's true". –  user16697 Nov 26 '11 at 13:00
I see, thank you. I am sorry for misinterpreting the comments. –  Phira Nov 26 '11 at 13:18

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.

-
Thank you. you have been very useful! –  Dominus_Mors Nov 25 '11 at 23:58

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)$.

-
Thank you. You have been very useful! –  Dominus_Mors Nov 25 '11 at 23:59