Gran $O$ vs Big $\Theta$

Question

Soy consciente de la gran teta de la notación $f = \Theta(g)$ si y sólo si existen constantes positivas $A, B$ $x_0 > 0$ tal que para todos los $x > x_0$ hemos $$ A|g(x)| \leq |f(x)| \leq B |g(x)|. $$ ¿Qué pasa si la condición es la siguiente: $$ C_1 + A|g(x)| \leq |f(x)| \leq C_2 + B |g(x)| $$ donde $C_1, C_2$ son posiblemente negativo? Ciertamente, puede decirse que sólo $f = O(g)$. Hay una generalizada $\Theta$ notación que permite a los cambios (por decir $C_1, C_2$)? En particular, estoy interesado en el caso especial: \begin{eqnarray} -C \leq f(x) - g(x) \leq C \end{eqnarray} para algunos positivos $C$. ¿Cómo se $f$ comparar a $g$ en este caso? Si $f$ $g$ son funciones positivas de $x$ que ambos divergen a $\infty$, es cierto que $f(x) = -C + g(x) + \Theta(1)$? ¿Qué es la adecuada notación asintótica en este caso?

Actualización Gracias por la aclaración de las respuestas. Ahora aquí es un poco más difícil pregunta. Supongamos $f$ es discreto y $g$ es continua. Supongamos, además, que como $x \to \infty$, la diferencia de $f(x) - g(x)$ es asintóticamente acotada en el intervalo de $[-C,C]$ pero no necesariamente convergen a $0$. Qué $f \sim g$ sentido todavía? Sería más adecuado utilizar el $\liminf_{x \to \infty} f(x) - g(x) = - C$$\limsup_{x \to \infty} f(x) - g(x) = C$?

Answer 1

Si $\lim |f(x)| = \lim |g(x)| = \infty$, entonces no hay ninguna diferencia entre los dos conceptos.

Si $f$$\Theta(g)$, entonces es un "desplazado" $\Theta(g)$$C_1 = C_2 = 0$.

Si $f$ es un "desplazado $\Theta(g)$,$\Theta(g)$ : Desde $\lim |g(x)| = \infty$ existe $x_1$ a partir de que $C_2/B \le |g(x)|$$ -2C_1/A \le |g(x)|$. Esto muestra que para $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)|$.

Si $-C \le f(x)-g(x) \le C$, entonces esto es exactamente lo mismo que decir $f-g = O(1)$. En este caso, usted tiene $f = g+O(1)$, y si su límite es $\pm \infty$, $f \sim g$

Answer 2

Si $g(x)$ $f(x)$ tiende a $\infty$, entonces no es un valor de $x_0$ tal que para $x > x_0$, $g(x)$ y $f(x)$ son estrictamente positivos. Por lo tanto, si $-C \leq f(x) - g(x) \leq C$,$x > x_0$, tenemos

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

Tomando límites, se puede ver que

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

si el límite existe. En este caso, usted puede escribir $f \sim g$.

Actualización: para responder A su segunda pregunta, $f \sim g$ puede no ser apropiado aquí como $\displaystyle\lim_{x \to \infty} \frac{f(x)}{g(x)}$ puede o no puede existir. Si el límite existe, entonces usted puede escribir $f \sim g$ como antes. Si no, entonces la situación es más complicada, y debe ser tratado de forma individual, dependiendo de las funciones $f$$g$. Usted sólo debe hacer la declaración que mejor ejemplifica lo que usted está tratando de decir entre la relación de $f(x)$$g(x)$. El big-Oh (o big-Theta) notación puede no ser la mejor opción aquí. Espero que esto sea útil.