Is $f(n) + O(f(n)) = \theta(f(n))$?

1.6k Views Asked by At

I've been asked to show whether this is always, never or sometimes true.

I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation is true, we can write:

$c_1f(n) \le f(n) + g(n) \le c_2f(n)$

For large enough $n$

But I'm not sure where to go from there, to prove whether the equation is true or not.

1

There are 1 best solutions below

4
On BEST ANSWER

Counterexample: $f(n)-f(n)=0\ne\theta(f(n))$ unless $f(n)=0$ for large $n$. (Clearly, $-f(n)=O(f(n))$.) Thus, sometimes this is not true. On the other hand, $f(n)+0=\theta(f(n))$, so in this case the claim is true. Thus, the answer is "sometimes true".