Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?
-
29-09-2020 - |
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))$
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)$