# Big $O$ vs Big $\Theta$

I am aware of the big theta notation $f = \Theta(g)$ if and only if there are positive constants $A, B$ and $x_0 > 0$ such that for all $x > x_0$ we have $$A|g(x)| \leq |f(x)| \leq B |g(x)|.$$ What if the condition is the following: $$C_1 + A|g(x)| \leq |f(x)| \leq C_2 + B |g(x)|$$ where $C_1, C_2$ are possibly negative? Certainly more can be said than just $f = O(g)$. Is there a generalized $\Theta$ notation which allows shifts (by, say $C_1, C_2$)? In particular, I'm interested in the special case: \begin{eqnarray} -C \leq f(x) - g(x) \leq C \end{eqnarray} for some positive $C$. How does $f$ compare to $g$ in this case? If $f$ and $g$ are positive functions of $x$ which both diverge to $\infty$, is it true that $f(x) = -C + g(x) + \Theta(1)$? What is the appropriate asymptotic notation in this case?

Update Thanks for the clarifying answers. Now here is a slightly harder question. Suppose $f$ is discrete and $g$ is continuous. Suppose further that as $x \to \infty$, the difference $f(x) - g(x)$ is asymptotically bounded in the interval $[-C,C]$ but does not necessarily converge to $0$. Does $f \sim g$ still make sense? Would it be more appropriate to use $\liminf_{x \to \infty} f(x) - g(x) = - C$ and $\limsup_{x \to \infty} f(x) - g(x) = C$?

-
@DJC: Edited. Thanks. – user02138 Feb 28 '11 at 17:43
Be careful. If $f(x)$ is discrete, then it is not defined everywhere. Hence, $f(x) - g(x)$ may not make sense. It would definitely make more sense to use your $\limsup$ and $\liminf$ notation. – JavaMan Feb 28 '11 at 18:31
@DJC: Both $f(x)$ and $g(x)$ are defined on the positive reals, but $f(x)$ is integer-valued. – user02138 Feb 28 '11 at 18:36

If $g(x)$ and $f(x)$ tends to $\infty$, then there is a value $x_0$ such that for $x > x_0$, $g(x)$ and $f(x)$ are strictly positive. Therefore, if $-C \leq f(x) - g(x) \leq C$, then for $x > x_0$, we have

$$\frac{-C}{g(x)} \leq \frac{f(x)}{g(x)} -1 \leq \frac{C}{g(x)}.$$

Taking limits, you see that

$$\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1,$$

if the limit exists. In this case, you can write $f \sim g$.

Update: To answer your second question, $f \sim g$ may not be appropriate here as $\displaystyle\lim_{x \to \infty} \frac{f(x)}{g(x)}$ may or may not exist. If the limit does exist, then you can write $f \sim g$ as before. If not, then the situation is trickier, and it must be dealt with individually, depending on the functions $f$ and $g$. You should just make the statement that best exemplifies what you are trying to say between the relationship of $f(x)$ and $g(x)$. The big-Oh (or big-Theta) notation may not be the best fit here. Hope this is helpful.

-

If $\lim |f(x)| = \lim |g(x)| = \infty$ then there is no difference between your two concepts.

If $f$ is a $\Theta(g)$, then it is a "shifted" $\Theta(g)$ with $C_1 = C_2 = 0$.

If $f$ is a "shifted $\Theta(g)$, then it is a $\Theta(g)$ : Since $\lim |g(x)| = \infty$, there exists $x_1$ from which $C_2/B \le |g(x)|$ and $-2C_1/A \le |g(x)|$. This shows that for $x \ge \max(x_0,x_1)$, $A|g(x)|/2 \le C_1 + A|g(x)| \le |f(x)| \le C_2 + B|g(x)| \le 2B|g(x)|$.

If $-C \le f(x)-g(x) \le C$, then this is exactly the same as saying $f-g = O(1)$. In this case, you have $f = g+O(1)$, and if their limit is $\pm \infty$, $f \sim g$

-