0

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!

STC
  • 11

1 Answers1

0

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.

quid
  • 42,135
  • but isn't f(n) = 1 a monotonically non-decreasing function? Is there an example that isn't a monotonically non-decreasing function? – STC Mar 01 '15 at 17:32
  • Yes, $f(n)$ is but $g(n)$ is not. If you want an example where both violate the consdtion take $f(n)=1/n$ and $g(n)=1/n^2$. – quid Mar 01 '15 at 17:37
  • So it's correct that if f(n) = 1/n and g(n) = 1/n^2,

    f(n) = O(g(n) + 2) but not true that f(n) = O(g(n))?

     – STC Mar 01 '15 at 19:27
  • Yes this is the case. – quid Mar 01 '15 at 19:29