Question

Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows:

$f(n) = c\cdot g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh.

So, $O(g(n))$ is substitutable for $c\cdot g(n)$:

$f(n) = O(g(n)) + O(g(n))$

And by the max rule of sum:

$f(n) = O(g(n))$

Was it helpful?

Solution

Firstly let me say, that in definition of big-O, for non negative case, there is inequality(not equality, typo I think): $$O(g)=\{f: \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$

Now $f(n) = c\cdot g(n) + O(g(n))$ means, that $\exists \phi (n) \in O(g(n))$ such that $f(n) = c\cdot g(n) + \phi (n)$. From here we have $$f(n) = c\cdot g(n) + \phi (n) \leqslant c\cdot g(n) + C\cdot g (n)=(c+C)g (n)$$ so $f \in O(g)$ and your claim is correct.

The general rule can be worded as follows:

If $f \in O(g)$, then $f+O(g)=O(g)$

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top