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

  • 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.