# Given that f(n)>0 and constant c>0 Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false

Question:

Given that f(n)>0 and c>0

Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false.

My Effort to solve: \begin{eqnarray*} f(n) + c \space \leq \space d\cdot&f(n)\space for \space all\space n \geq n_0\space and \space d>0\\ \end{eqnarray*} So i believe there can be found some large d that satisfies this equation, but i am not sure about it.

• @Complexity the problem is, this equation actually may be wrong and only true if f(n)>=1, but I don't know why. – codemonkey Feb 17 '18 at 16:35
• Is $f(n)$ integer-valued? – Yuval Filmus Feb 17 '18 at 16:59
• Your "effort to solve" doesn't match the definition of Big-O. – gnasher729 Feb 17 '18 at 19:13
• @gnasher729 why? – codemonkey Feb 18 '18 at 10:12
• @codemonkey Well, you changed it since my comment. And it's still misleading: You must show the inequality for one fixed d > 0, and for all n ≥ n0. – gnasher729 Feb 18 '18 at 11:04

This is false. A counterexample is $f(n)=1/n$ and $c=1$.
If $f(n)+c=O(f(n))$, then there exists $n_0>0$ and $d>0$, for any $n>n_0$, $f(n)+c\le df(n)$, or $1/n+1\le d/n$. But let $n=\max\{n_0+1,d\}$, the inequality fails obviously, a contradiction.
In fact, any $f(n)$ and $c$ such that $f(n)\to 0$ ($n\to\infty$) and $c>0$ are sufficient.
• @codemonkey The intent is to make $n>n_0$ and $n>d-1$. – xskxzr Feb 17 '18 at 17:50