0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 27 '15 at 7:54
2
$\begingroup$

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.

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

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.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.