# Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?

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 is this always true only for positive monotonically non-decreasing functions? $\Theta$

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!

• General note: The mere fact that you have a theorem $A \implies B$ does not imply that $\lnot A \implies \lnot B$ (which you seem to be assuming). Maybe we were just not able to prove more even though it's true, or we didn't bother. And there certainly may be examples for which the rule holds but which don't collectively have a nice characterisation. – Raphael Feb 27 '15 at 7:54

## 2 Answers

Let $f(n) = 1-1/n$ and $g(n) = 1/n$, so we've violated the condition that $g$ is non-decreasing. However, it's not hard to show that $f(n) \in O(g(n)+2)$ but we also have $f(n)\notin O(g(n)$, invalidating the inference.

• but isn't f(n) = 1 - 1/n a monotonically non-decreasing function? Is there an example that is not monotonically non-decreasing? – STC Mar 1 '15 at 17:30
• oh ok, so 1-1/n is monotonic but not non-decreasing. got it, thanks. – STC Mar 1 '15 at 17:48

More generally, if $f(n) = O(g(n)+h(n))$ and $g(n) = \Omega(h(n))$ then $f(n) = O(g(n))$. If, on the contrary, $g(n) = o(h(n))$, then $f(n) = O(h(n))$. (It could also be that neither conditions hold.)