1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Complexity the problem is, this equation actually may be wrong and only true if f(n)>=1, but I don't know why. $\endgroup$ – codemonkey Feb 17 '18 at 16:35
  • 1
    $\begingroup$ Is $f(n)$ integer-valued? $\endgroup$ – Yuval Filmus Feb 17 '18 at 16:59
  • $\begingroup$ Your "effort to solve" doesn't match the definition of Big-O. $\endgroup$ – gnasher729 Feb 17 '18 at 19:13
  • $\begingroup$ @gnasher729 why? $\endgroup$ – codemonkey Feb 18 '18 at 10:12
  • $\begingroup$ @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. $\endgroup$ – gnasher729 Feb 18 '18 at 11:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why let n = max {n_0 + 1,d} ? $\endgroup$ – codemonkey Feb 17 '18 at 17:39
  • $\begingroup$ @codemonkey The intent is to make $n>n_0$ and $n>d-1$. $\endgroup$ – xskxzr Feb 17 '18 at 17:50

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.