-1
$\begingroup$

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.

  • 8
    It is not even close to rude to ask us to hurry up. It is much worse.2011-11-25
  • 3
    Where does it say "hurry up"?2011-11-25
  • 0
    @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.2011-11-26
  • 0
    @Phira, I disagree2011-11-26
  • 0
    @QED With what? I am confused by your comment.2011-11-26
  • 2
    @Phira, "if lots of people say something then it's true".2011-11-26
  • 0
    @Phira: There was no comment. I posted this because of a time frame "given" in the second line. Timelines have nothing to do with the content of the question. This is not as explicit as that person asking us to solve his take home exam, but I find that addition hinting as if "we should hurry up and help quickly".2011-11-26
  • 1
    I see, thank you. I am sorry for misinterpreting the comments.2011-11-26

2 Answers 2

1

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

0

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.