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

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion centers on proving that if \( f(n) = O(g(n)) \) and \( \lim_{n \to +\infty} f(n) = +\infty \), then \( f(n) + c = O(g(n)) \) for any constant \( c > 0 \). Participants clarify that while \( f(n) + c \) is indeed \( O(g(n)) \), it does not necessarily imply \( f(n) = \Theta(g(n)) \). The conversation emphasizes that for \( c = 0 \), the statement holds trivially, while for \( c > 0 \), the proof remains valid. There is a consensus that the original argument may have overreached by suggesting a stronger conclusion than warranted. The thread concludes with a focus on the implications of the limits and the behavior of the functions involved.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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 $$
 
Physics news on Phys.org
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))$.
 
Evgeny.Makarov said:
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)
 
evinda said:
I see (Nod) But it holds for all $c>0$.
What do you see and what holds for all $c>0$?
 
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)
 
evinda said:
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.

Evgeny.Makarov said:
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))$.
 

Similar threads

Back
Top