0
$\begingroup$

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$.

I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ .

$f(n)=O(g(n))$

That means that $\exists c_1>0, n_2 \in \mathbb{N}$, such that $\forall n \geq n_2$:

$$f(n) \leq c_1 g(n)$$

$\lim_{n \to +\infty} f(n)=+\infty$

This means that $\forall \epsilon>0 \ \exists n_0$, such that $\forall n \geq n_0$, $$f(n)> M$$

How can we use this, in order to show that $f(n)+c=O(g(n))$ ?

$\endgroup$
  • 1
    $\begingroup$ This is false, $c = O(1)$ for any $c\in\mathbb R$, so you can set $f=0$. $\endgroup$ – user2345215 Nov 29 '14 at 14:30
  • 2
    $\begingroup$ The assumption that $f(n)=O(g(n))$ and $f(n)+c=O(g(n))$ does not imply that $\lim\limits_{n \to +\infty} f(n)=+\infty$ (even assuming $c\ne0$). $\endgroup$ – Did Nov 29 '14 at 14:30
  • $\begingroup$ I edited my post.. Does it make sense now? $\endgroup$ – evinda Nov 29 '14 at 14:38
1
$\begingroup$

Here is a (stronger) result (with an easier proof) which implies yours:

Assume that $\liminf |f|\gt0$, then, for every finite $c$, $f+c\in O(f)$.

To apply this to your setting, note that the hypothesis that $\lim f=+\infty$ implies that $\liminf |f|\gt0$, and that if $f+c\in O(f)$ and $f\in O(g)$ then $f+c\in O(g)$.

Now can you prove the result above? One should start with the hypothesis that $\liminf |f|\gt0$, hence $|f(n)|\geqslant a$ for some $a\gt0$, for every $n$ large enough, say, for every $n\geqslant N$, hence $|f(n)+c|\leqslant$ $____$ for every $n\geqslant N$, hence...

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