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!

Improve this question
$\endgroup$
1
  • $\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
    Commented Feb 27, 2015 at 7:54

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Mar 1, 2015 at 17:30
  • $\begingroup$ oh ok, so 1-1/n is monotonic but not non-decreasing. got it, thanks. $\endgroup$
    – STC
    Commented Mar 1, 2015 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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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