Determine si $F(x)= 5x+10$ es $O(x^2)$

Question

Por favor, ¿alguien puede ayudarme a entender la notación Big-O en matemáticas discretas?

Determine si $F(x)= 5x+10$ es $O(x^2)$

Answer 1

Demos una definición de la notación Big-O:

Supongamos que $g(x)\geq 0$ . Decimos que $f(x)=O(g(x))$ como $x\rightarrow\infty$ si:

Loosely : $\lvert f(x)\rvert$ está limitada por un múltiplo constante de $g(x)$ para $x$ suficientemente grande.

Rigurosamente : Existe $C>0$ y $X\in \mathbb{R}$ tal que para todo $x>X$ tenemos $\lvert f(x)\rvert \leq Cg(x)$ .

En su caso, nos ocupamos de $f(x)=5x+10$ . Por lo tanto, queremos demostrar que para $x$ suficientemente grande, $f(x)$ puede ser acotado por $Cx^2$ para algunos $C$ .

Para simplificar la vida, vamos a suponer $x\geq 10$ para que $\lvert 5x+10\rvert=5x+10\leq 5x+x=6x$ . Ahora bien, si $x\geq 10$ entonces $x\leq x^2$ . Así, para $x\geq 10$ tenemos $$ \lvert 5x+10\rvert=5x+10\leq 6x\leq 6x^2. $$ Por lo tanto, es cierto que $5x+10=O(x^2)$ como se le pidió.

La gran idea de la notación Big-O es la siguiente: todo lo que te pide es que pienses en el tasa de crecimiento de la función, una vez $x$ es lo suficientemente grande como para que sólo importen los términos principales. En este caso, el orden exacto de su función es $x$ para $x\rightarrow\infty$ Por supuesto. $x^2$ es una tasa de crecimiento más rápida que $x$ es.

Answer 2

A problema relacionado . Puede utilizar el hecho

$$f=O(g)\quad \rm{iff} \quad \limsup_{x \to \infty}\frac{|f(x)|}{|g(x)|} =c,$$

donde $c$ es finito.

Answer 3

Es como $x \to \infty$ . En realidad, $5x+10 = o(x^2)$ como $x \to \infty$ (pequeño-oh) desde $\lim_{x \to \infty} \frac{5x+10}{x^2} = 0$ .

Sin embargo, $5x+10 \ne O(x^2)$ como $x \to 0$ , y $5x \ne O(x^2)$ como $x \to 0$ , porque no hay un verdadero $c$ tal que $5x < c x^2$ como $x \to 0$ .

Desde $x \to 0$ y $x \to \infty$ son los dos límites comunes límites para la notación big-oh, es importante indicar a cuál de ellos se refiere.

Answer 4

Respuesta corta:
Sí, es $\mathcal{O}(x^2)$ .

Respuesta larga:
Veamos la definición de $\mathcal{O}$ :

$f(x) = \mathcal{O}(g(x))$ si y sólo si existe un número real positivo $M$ y un número real $x_0$ tal que: $$|f(x)| \le M|g(x)| \text{ for all } x \gt x_0$$

En términos sencillos, se trata de decir que $\mathcal{O}(g(x))$ es un límite superior a la función. Básicamente, en algún momento, $g(x)$ crece tan rápido o más que $f(x)$ .

Claramente, $x^2$ finalmente supera a $x$ en términos de crecimiento a largo plazo. En el "largo plazo", (como $x \to \infty$ ), no importa lo que se añada a $x$ o que $x$ se multiplica por $x^2$ lo vencerá. Así, $x^2$ es un límite superior.

(Este es un argumento no riguroso, por supuesto. En lugar de probarlo para usted, esto es sólo para dar una idea de cómo $\mathcal{O}$ obras).