Proving $f(n)+c=O(g(n))$ with $\lim_{n \to +\infty}f(n)=+\infty$

[evinda]

Hi! (Smile)

I want to show that $f(n)=O(g(n))$ and $\lim_{n \to +\infty} f(n)=+\infty$ implies that $f(n)+c=O(g(n))$.

$f(n)=O(g(n))$ means that $\exists c_1>0, n_1 \in \mathbb{N}_0$ such that $\forall n \geq n_1$: $f(n) \leq c_1g(n)$.

$\lim_{n \to +\infty} f(n)=+\infty$ means that $\forall M>0 \exists n_2 \in \mathbb{N}_0$ such that $\forall n \geq n_2$: $f(n)>M$.

We want to show that $\exists c_2>0, n_0 \in \mathbb{N}_0$ such that $\forall n \geq n_0$: $f(n)+c<c_2 g(n)$

That's what I have tried:$$M<f(n) \leq c_1 g(n) \Rightarrow M+c < f(n)+c \leq c_1g(n)+c \Rightarrow \frac{M+c}{g(n)} < \frac{f(n)+c}{g(n)} \leq \frac{ c_1g(n)+c}{g(n)} \Rightarrow \lim_{n \to +\infty} \frac{M+c}{g(n)}< \lim_{n \to +\infty} \frac{f(n)+c}{g(n)} \leq \lim_{n \to +\infty} \frac{ c_1g(n)+c}{g(n)} \overset{\star}{\Rightarrow} 0<\lim_{n \to +\infty} \frac{f(n)+c}{g(n)} \leq c_1 \\ \Rightarrow \lim_{n \to +\infty} \frac{f(n)+c}{g(n)}=a \in (0,c_1] \Rightarrow f(n)+c=\Theta(g(n)) \Rightarrow f(n)+c=O(g(n)) $$$$ \star: f(n) \leq c_1 g(n) \wedge \lim_{n \to +\infty} f(n)=+\infty \Rightarrow \lim_{n \to +\infty} c_1 g(n)=+\infty \Rightarrow \lim_{n \to +\infty}g(n)=+\infty $$

 

[Evgeny.Makarov]

I think you proved too much. Take $c=0$. The fact that $f(n)=O(g(n))$ and $\lim_{n \to +\infty} f(n)=+\infty$ does not imply that $f(n)=\Theta(g(n))$.

 

[evinda]

I think you proved too much. Take $c=0$. The fact that $f(n)=O(g(n))$ and $\lim_{n \to +\infty} f(n)=+\infty$ does not imply that $f(n)=\Theta(g(n))$.

I see (Nod) But it holds for all $c>0$.. Or am I wrong? (Thinking)

 

[Evgeny.Makarov]

I see (Nod) But it holds for all $c>0$.

What do you see and what holds for all $c>0$?

 

[evinda]

For $c=0$ we don't have to show anything since $f(n)=O(g(n))$ and $\lim_{n \to +\infty} f(n)=+\infty$ trivially implies that $f(n)+c=O(g(n))$.

For $c>0$ that what I wrote holds, or not? (Thinking)

 

[Evgeny.Makarov]

For $c=0$ we don't have to show anything since $f(n)=O(g(n))$ and $\lim_{n \to +\infty} f(n)=+\infty$ trivially implies that $f(n)+c=O(g(n))$.

Slowly exhales. Let's try this again.

The fact that $f(n)=O(g(n))$ and $\lim_{n \to +\infty} f(n)=+\infty$ does not imply that $f(n)=\Theta(g(n))$.

I said this because you deduced $f(n)+c=O(g(n))$ from $f(n)+c=\Theta(g(n))$.