0
$\begingroup$

I want to prove the following by the definition

  1. $$|f(n)-g(n)|\in \mathcal{O}(t(n)) $$
  2. $$f(n)+g(n)\in \Omega(t(n))$$

Is it true that $f(n)\in \Omega(t(n))$?
What I tried is just think about functions, it seems true, but I don't know how to prove it in formal way.
For Example:

  • $f(n)=n^6$
  • $g(n)=n^4$
  • $t(n)=n^6$
$\endgroup$

1 Answer 1

0
$\begingroup$

No, this is not true.. Just turn around your example.. i.e. $f(n) = n^4$, $g(n) = n^6$, $t(n) = n^6$. Then both your given conditions are true, but $f(n) \notin \Omega(t(n))$.

$\endgroup$
1
  • $\begingroup$ Should I add the definition of $\Omega$ or its enough to say that? $\endgroup$
    – Ofir Attia
    Mar 29, 2014 at 15:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .