Notación O

Motivación

• Nos interesan más la forma de la curva
• Podemos descartar lo que pasa a los primeros números de n

Por lo que:

• no interesan los factores constantes
• no interesan los valores que toma la función cuando n es chico.

Propiedades y lemas

def. Sean $f,g: \Bbb{N} \rightarrow \Bbb{R}^+ $, decimos que $ f \in O(g) $ si existen una constante c > 0 y un $ n_0 \in \Bbb{N}$ tales que para todo $ n \geq n_0$ vale:

$ f(n) \leq c.g(n) $

• f es mas chica que g :/
• g domina a f asintóticamente :)

Ejemplos

$ n \in O(n+5) $

Si tomo $ c = 1, n_0 = 1 $

$ n \leq 1.(n+5) \forall n \geq 1$

¿y al revés?

$ n+5 \in O(n) $

Si tomo $ c = 2, n_0 = 5 $

$ n+5 \leq 2.n\ \forall n \geq 5$

Lema. Si $ f_1,f_2 \in O(g)$ entonces $f_1 + f_2 \in O(g) $

Dem. Sean $ f_1,f_2 \in O(g) $

Como $ f_1 \in O(g)$, existen $ c_1 > 0 $ y un $ n_1 \in \Bbb{N} $ tales que:

$ f_1(n) \leq c_1.g(n)\ \forall n \geq n_1 $

Análogamente, existen $ c_2 > 0 $ y un $ n_2 \in \Bbb{N} $ tales que:

$ f_2(n) \leq c_2.g(n)\ \forall n \geq n_2 $

Si tomamos $ c = c_1 + c_2 $ y $ n_0 = máx { n_1, n_2 } $

$ f_1(n) + f_2(n) \leq c_1.g(n) + f_2(n) $

$ \leq c_1.g(n) + c_2.g(n) = (c1+c2)*g(n) $

$ = c.g(n)\ \forall n \geq n_0 $

$ f_1(n) + f_2(n) \leq c.g(n)\ \forall n \geq n_0 $

Que es lo que queríamos probar.

Ejemplos.

$ 3n^2 + n \in O(n^2) $

Por el lema anterior con probar que $ 3n^2 \in O(n^2) $ y $ n \in O(n^2) $, estamos.

Para $ 3n^2 \in O(n^2) $ con $ c=3 $ y $ n=1 $.

Para $ n \in O(n^2) $ con $ c=1 $ y $ n=2 $.

Luego nos quedamos con el c=3 y n=2 y esta resuelto.

Lema. Si $ f:\Bbb{N} \rightarrow \Bbb{R}^+$ es una función poliniomal, es decir:

$ f(n) = a_0 + a_1.n + a_2.n^2 + … + a_d.n^d $

Y sabiendo que $ a_d \neq 0 $.

Entonces:

$ f \in O( n^d ) $

• Llamamos grado(p) = d

Ejemplo. $ n \notin O(1) $.

Dem. Se prueba por absurdo. Suponemos que sí, entonces c > 0 y un $ n_0 \in \Bbb{N} $ tal que:

$ n \leq c\ \ \forall n \geq n_0 $

Pero esto es como suponer que ahí una constante superior a todos los naturales, y sabemos que no importa cuan grande sea una constante, si le calculamos el techo y le sumamos 1 tenemos un natural mayor.

Ejemplo. $ n^2 \notin O(n) $.

Dem. También se prueba por absurdo. Suponemos que sí, entonces c > 0 y un $ n_0 \in \Bbb{N} $ tal que:

$ n^2 \leq c.n\ \ \forall n \geq n_0 $

Si divido ambos lados por n…

$ n \leq c\ \ \forall n \geq n_0 $

Lo que en el caso anterior dijimos que era una contradicción.

Propiedad transitiva

Si $ f \in O(g)$ y $ g \in O(h)$ entonces $ f \in O(h)$

dem. Sean $ f \in O(g) $

Como $ f \in O(g)$, existen $ c_1 > 0 $ y un $ n_1 \in \Bbb{N} $ tales que:

$ f(n) \leq c_1.g(n)\ \forall n \geq n_1 \ \ (1) $

Y tambien $ b \in O(h) $

Como $ g \in O(h)$, existen $ c_2 > 0 $ y un $ n_2 \in \Bbb{N} $ tales que:

$ g(n) \leq c_2.h(n)\ \forall n \geq n_2 \ \ (2) $

Supongamos que $ c_2 $ es igual al cociente de dos constantes c y $ c_1 $, y que $ n_0 = máx {n_1, n_2} $.

$ g(n) \leq \frac{c}{c_1}.h(n)\ \forall n \geq n_0 \ \ (3) $

Múltiplico ambos terminos por $ c_1 $.

$ c_1.g(n) \leq c.h(n)\ \forall n \geq n_0 \ \ (4) $

Por la ecuacion (1) sabemos:

$ f(n) \leq c_1.g(n) \leq c.h(n)\ \forall n \geq n_0 \ \ (4) $

Que es lo que queríamos probar.

Logaritmos. $ log_a(n) \in \mathcal{log_b(n)} $.

Sabemos que:

$ log_a(n) = x donde a^x = n $

$ log_b(n) = x donde b^x = n $

¿Son válidas estas afirmaciones?

$ log_3(n) \in? \mathcal{ log_2(n)} $
$ log_2(n) \in? \mathcal{ log_3(n)} $

Lema. Órden de los logaritmos.

Si a,b > 1 entonces $ log_a(n) \in \mathcal{log_b(n)} $

Dem. Recordemos que $ log_a(n) = \frac{log_b(n)}{log_b(a)} $.

Tomamos los términos. $ log_b(n) = x $
$ log_b(a) = y $

Entonces $ b^x = n, b^y = a $.

Por lo que $ a^{1/y} = (b^y)^{1/y} = b $

Y $ a^{1/y} = (b^y)^{1/y} = b $

Y $ a^{x/y} = (a^{1/y})^{x} = b^x = n $

Por lo que $ log_a(n) = x / y = \frac{log_b(n)}{log_b(a)} $.

Entonces como la relación entre cualquier par de logaritmo es un número constante, es fácil obtener una constante para ajustar a c.

Ejemplo. $ 2^n \in O(3^n) $.

Esto se ve $ 2^n \leq 3^n\ \forall\ n \geq n_0 $

Y al revés? $ 3^n \in O(2^n) $?

Vimos que la suma de órdenes vale, pero ¿que pasá con el producto f_1 * f_2?

Formalmente, si $ f_1,f_2 \in O(g)$ entonces $f_1 . f_2 \in O(g) $?

Supongamos que $ g(n) = n, f_1(3n) $ y $ f_2(2n) $, $ f_1(n).f_2(n) = 3n.2n. = 6n^2 $ que vimos más arriba que no está en el órden de n.

Lema. Si $ f_1 \in O(g_1)$ y $ f_2 \in O(g_2)$, entonces $ f_1.f_2 \in O(g_1.g_2)$

Lema. “Exponenciales domina líneal”

$ n \in O(2^n) $

dem. Por inducción.

1) Para n=1:

$ 1 \leq 2^1 = 2$

2) $ P(n) \rightarrow P(n+1) $

Por HI podemos suponer que $ n \leq 2^n $.

Entonces:

$ n + 1 \leq 2^n + 1 \leq 2^n + 2^n = 2.2^n = 2^{n+1} $

Con lo que llegamos a la conclusión que queríamos probar.

Lema. “Lineal domina a logarítmica”

$ log(n) \in O(n) $

Dem. Veamos que $ log_2 \leq n $

Del punto anterior vimos que:

$ n \leq 2^n $

Aplicando a ambos miembros una función monótona creciente como el logaritmo:

$ log(n) \leq log_2(2^n) = n $.

Que es lo que queríamos probar.

Teorema. “Exponencial domina a polinomial”

Si $ p \geq 0$, $ n^p \in O(2^n) $

Dem. Afirmo: $ \forall k \in \Bbb{N} $ vale:

$ ({\frac{n}{p}})^k \leq ({2^{n/p}})^k $

Si k = p, $ \forall n \geq p $, tendriamos que:

$ ({\frac{n}{p}})^p \leq ({2^{n/p}})^p $

Lo que equivale a que:

$ ({\frac{n^p}{p^p}}) \leq 2^{n} $

$ n^p \leq p^p.2^n\ \ \forall n \geq p $

Si tomamos p^p como c y p como $n_0$ obtuvimos lo que queríamos probar.

$ n^p \leq c.2^n\ \ \forall n \geq n_0 $

Otras Notaciones utilizadas

Definición de $ \omicron $

Vamos a usar la definición del libro de Michael Sipser, basada en límite.

def. Sean $f,g: \Bbb{N} \rightarrow \Bbb{R}^+ $, decimos que $ f \in \omicron(g) $ si vale:

$\lim_{n \to +\infty} \frac{f(x)}{g(x)} = 0$

Es decir, $\forall\ \epsilon > 0$, $\exists n_0 \in \Bbb{N}\ \forall n \geq n_0 $ tal que:

$ \frac{f(n)}{g(n)} < \epsilon $

Ejemplos

$ n \in \omicron(n^2)$, $ n \in O(n^2) $

$ 2n \in O(n)$, pero $ 2n \notin \omicron(n) $

Expresiones con Notación $O$