Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
8  
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
3  
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
2  
@Phira, "if lots of people say something then it's true". –  user16697 Nov 26 '11 at 13:00
1  
I see, thank you. I am sorry for misinterpreting the comments. –  Phira Nov 26 '11 at 13:18

2 Answers 2

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.

share|improve this answer
    
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)$.

share|improve this answer
    
Thank you. You have been very useful! –  Dominus_Mors Nov 25 '11 at 23:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.