Tarea 1 de Aplicaciones a la Computacion
Diego Carvajal
29 de Marzo 2015
Introducci
on
En este trabajo veremos demostraciones de 8 propiedades que salen de la definicion del conjunto de
todas las funciones dominadas por una cota superior llamada comunmente como Big O o la Notaci
on
de Landau, que es ocupada para la comparacion asintotica de funciones.
Notaci
on de Landau
Definici
on: Sea f : N [0, ). Se define el conjunto de funciones de orden O (Omicron) de f
como:
O(f ) = {g : N [0, ) : (c R+ )(n0 N), g(n) cf (n) n n0 }
Diremos que una funci
on t : N [0, ) es de orden O de f si t O(f ).
2.1
Propiedades
1. Para cualquier funci
on f se tiene que f O(f ).
2. f O(g) O(f ) O(g).
3. O(f ) = O(g) f O(g) y g O(f ).
4. Si f O(g) y g O(h) f O(h).
5. Si f O(g) y f O(h) f O(min(g, h)).
6. Regla de la suma: Si f1 O(g) y f2 O(h) f1 + f2 O(max(g, h)).
7. Regla del producto: Si f1 O(g) y f2 O(h) f1 f2 O(gh).
(n)
8. Si existe limn fg(n)
= k, dependiendo de los valores que tome k obtenemos:
a) Si k 6= 0 y k < entonces O(f ) = O(g).
b) Si k = 0 entonces f O(g), es decir, O(f ) O(g), pero sin embargo se verifica que g
/ O(f ).
2.2
Demostraci
on
1. Sea f : N [0, ), entonces sabemos que existe un c R mayor que cero tal que todas las
funciones g : N [0, ) est
an acotadas superiormente por un f n n0 . Claramente podemos
notar que f (n) cf (n) n, luego f (n) cf (n) n n0 . Por lo tanto f O(f ).
2. Si f : N [0, ) est
a en O(g), entonces existe un c R mayor que cero tal que f (n) cg(n)
1
n n0 . Tomemos c = d , entonces
f (n)
g(n)
d
n n0
df (n) g(n) n n0
f (n) df (n) g(n) n n0
f (n) g(n) n n0
Por lo tanto, O(f ) O(g).
3. Afirmacion: Si O(f ) = O(g) f O(g) y g O(f ). En efecto, como O(f ) = O(g), entonces
existen c y d R mayores que cero tales que
dg(n) f (n) cg(n) n n0
Luego como existe un c tal que f (n) cg(n) n n0 , entonces f O(g), de manera analoga se tiene
para g O(f ).
Afirmacion: Si f O(g) y g O(f ) O(f ) = O(g). En efecto, como f O(g), entonces existe un real c > 0 tal que f (n) cg(n) n n0 y de forma analoga se tendra un real c0 > 0 tal que
g(n) c0 f (n) n n1 , esto implica que
g(n) c0 f (n) cc0 g(n) n max(n0 , n1 )
De esto se deduce que O(f ) = O(g).
4. Como f O(g) y g O(h), entonces de forma analoga propiedad 3, existiran c0 y c reales
positivos tales que
1
c f (n) g(n) c0 h(n) n max(n0 , n1 )
1
c f (n)
c0 h(n) n max(n0 , n1 )
f (n) cc0 h(n) n max(n0 , n1 )
Por lo tanto, f O(h).
5. Si f O(g) y f O(h), entonces existen reales positivos c0 y c1
f (n) c0 g(n) n n0 f (n) c1 h(n) n n1
Como el conjunto O se encarga de tener todas las funciones que esten mas abajo de una cota superior,
a nosotros nos interesa la menor de las cotas superiores, por lo tanto f O(min(g, h))
6. Si f1 O(g) y f2 O(h), entonces existen reales positivos c1 y c2 tales que
f1 (n) c1 g(n) n n1 f2 (n) c2 h(n) n n2
f1 (n) + f2 (n) c1 g(n) + c2 h(n) n max(n1 , n2 )
Necesitamos que f1 (n) + f2 (n) este acotado superiormente por una funcion con una constante para
todo n mayor o igual que max(n1 , n2 ), entonces tenemos que acotar a
un mas la funcion con la funci
on
de mayor crecimiento para as para estar a la par con la definicion de O, lo que implica que
f1 (n) + f2 (n) kmax(g(n), h(n)) n max(n1 , n2 )
Donde k es una constante igual que 2c1 o 2c2 , dependiendo de cual sea el maximo.
7. Para este caso, nosotros tendremos
f1 (n)f2 (n) c1 c2 g(n)h(n) n max(n1 , n2 )
Por lo tanto, f1 f2 O(gh).
(n)
8. Suponiendo que existe limn fg(n)
= k, veamos el primer caso
a) k 6= 0 y k < . Entonces, por definici
on de lmite, dado un > 0, existe un n0 N, n n0 tal
que
f (n)
<
k
g(n)
<
f (n)
g(n)
k <
g(n) < f (n) kg(n) < g(n)
g(n) + kg(n) < f (n) < g(n) + kg(n)
( + k)g(n) < f (n) < ( + k)g(n)
Ahora bien, el lo podemos tomar tan peque
no como queramos y aparte k es mayor que cero, ya
que es el resultado de dos funciones con recorrido en [0, ), entonces de la ultima desigualdad al igual
que en las demostraciones anteriores, podemos concluir que O(f ) = O(g).
b) Si k = 0, entonces
g(n) < f (n) < g(n)
De la desigualdad de la derecha y por la propiedad 2, podemos concluir que O(f ) O(g), pero para
la parte izquierda, tendremos una constante menor que cero, por lo tanto no se cumple la definici
on
para el conjunto O(f ), luego g
/ O(f ).
