I know that for positive monotonically non-decreasing functions, f(n) and g(n),
f(n) = O(g(n) + c) entails
f (n) = O(g(n))
Why does this always true only for positive monotonically non-decreasing functions?
If there exists one, give a counter-example that shows that the above Big O rule is not necessarily true for functions that are not monotonically non-decreasing.
I'm really confused why the rule specifies only positive, monotonic, non-decreasing functions. Thanks for your help!
Consider $f(n)= 1$ and $g(n)= 1/n$ then $f(n) = O(g(n) +1)$ but $f(n)$ is not a $O(g(n))$.
So you see that some condition is needed.
To say it only holds for for positive monotonically non-decreasing functions is not completely precise, as there are other $g$ where it also holds true, for exaple it would be true for $g(n)= 10 + n + 3(-1)^n$.
To see it does hold under the conditions you gave note that $g(n) \ge g(1)$. So you can say $g(n)+ C \le g(n)+ (C/g(1)) g(1) \le g(n) (1 + C/g(1))$.
So if $|f(n)| \le D (g(n) + C) $ for some $D$, then $|f(n)| \le (D (1 + C/g(1)) )g(n)$. This yields the claim.