Formalmente demostrar que una función es $O(x^n)$

Question

Decir que tengo una función

\begin{equation*} f(x) = ax^3 + bx^2 + cx + d,\text{ where }a > 0. \end{ecuación*}

Es claro que para un valor suficientemente alto de $x$, $x^3$ plazo va a dominar y puedo decir $f(x) \in O(x^3)$, pero esto no parece muy formal.

La definición formal es $f(x) \in O(g(x))$ si las constantes de $k, x_0 > 0$ existen, de tal manera que $0 \le f(x) \le kg(x)$ todos los $x > x_0$.

Mi pregunta es, ¿cuáles son los valores adecuados para $k$$x_0$? Es bastante fácil encontrar el que se aplican (por decir $k = a + b + c + d$). Por la definición formal, todo lo que tienes que hacer es mostrar que estos números existen, así que es lo que realmente importa en qué número debo usar? Para un cierto valor de $x$, $k$ podría estar en cualquier lugar de$1$$a + b + c + d + ... $. Desde mi entender, no importa lo que los números cojo mientras que 'trabajo', pero esto es correcto? Parece demasiado fácil.

Gracias

Answer 1

SUGERENCIA $\quad\rm ax^3 + bx^2 + cx + d\ \le \ (|a|+|b|+|c|+|d|)\ x^3 \ $ $\rm\ x > 1$

Answer 2

Suponga que tiene una función de $f(x)$$g(x)$.

Realmente un método sencillo (que funciona al $f(x)$ $g(x)$ son polinomios) de la determinación de una constante que funciona es la siguiente. Considere la posibilidad de

$\lim_{x\rightarrow\infty}\frac{f(x)}{g(x)}$

Si el límite existe y si una constante $0\leq C< \infty$. A continuación, $C+\epsilon$ cualquier $\epsilon>0$ es una constante que funciona. Para ver esto basta con aplicar la definición de límite. $\forall \epsilon>0$ existe un $x_0(\epsilon)$ tal que $\forall x>x_0(\epsilon)$ hemos

$\left|\frac{f(x)}{g(x)}-C\right|<\epsilon$

Que es

$\frac{f(x)}{g(x)} < C+\epsilon$

Ahora usted sabe que la constante de calcular el límite y saber de la existencia de $x_0$. Puesto que usted está considerando siempre asymptotics cuando se utiliza esta definición, usted nunca está relacionada con el valor de $x_0$ (la única que existe)

No importa lo que las constantes de utilizar y alguien podría fácilmente hacer uso de las diferentes constantes para obtener $f(x)=O(g(x))$. Esta notación es comparar la tasa de crecimiento de dos funciones.

Si $\lim_{x\rightarrow \infty} \frac{f(x)}{g(x)}$ no existe o es difícil de calcular, a continuación, como usted puede enlazar por encima de usted todavía tiene $f(x)=O(g(x))$