Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
@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
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.