Funciones Generatrices

CC40A - Gu a 1
19 de Marzo de 1997

1 Ordenando Funciones
1. Ordene las siguientes funciones en orden O() creciente, indicando los grupos que tienen el p mismo orden: n, n log n, n2 , n1 3 +logn, ln n, (1=3) , n, n n3 +7n5 , n3 , (log n)2 , n= log n, (3=2) , 2 , n2 + log n, log n, n!, log log n, 6. 2. Haga lo mismo con las siguientes funciones: log n, n2 =(log n)2 , n3 2, n2 = log n, n2 , n=log n, pn, 1, 1=n, 5 , n1 00001, n, log log n, n , (log n)2, n 2 , 2 , (log n) , nlog . 3 3. De las funciones de la lista anterior (ordenadas) elija la que representa un mejor O() y la que representaun mejor () para las siguientes: 1= log n, 7n5 3n + 2, (n2 + n)=(log2 n + log n), 2(log )2 , 3 . p p 4. Diga si es cierto o no: n2 es O(n3), n3 es O(n2 ), 2n2p 1 es O(n2 ), n log np O(n n), n es + esp O(log n), log n es O( n), n3 es O(n2 (1+ n2p n2 (1+ n) es O(n2 ), n2 (1+ p) es O(n2 log n), pn es O(n2), 3n2 + pn es O(n + n )), + pn), log n + pn es O(n), nn log n es O(n), 3n2 + n p p 1=n esO(log n), log n es O(1=n), log n es O(n 1 2), n + n es O( n log n). 5. De los siguientes pares f y g , determine si f es p (g ), (g ), (g ), o(g ) o ! (g ): n2 + 3n + 4 O p p vs 6n + 7, n vs log(n + 3), nn vs n2 n, n n vs 4n log(n2 + 1),(n2 + 2)=(1 + 2 ) vs n + 3, 2 n2 vs n4 + n2 , n log n vs (log n)log , n2 vs 3 , 100n + log n vs n + (log n)2 , log n vs log log n2 , (log n)106 vs n10 6 .
= n n n =n : n n n n n n n = n n n n n

2 Manipulacion de

O()

Se puede de nir O(g (n)) como el conjunto de todas las funciones que son O(g (n)). As , \f (n) es O(g (n))" se puede reescribir como f (n)2 O(g (n)). Abusando de la notacion se dice f (n) = O(g (n)). En los siguientes ejercicios, sea e(n) = o(1), f (n) = O(g (n)) y f (n) = (h (n)). Pruebe que 1. O(O(f (n)) = O(f (n)). 2. f1 (n) + f2 (n)= O(g1(n)) + g2 (n)) y (h1 (n) + h2 (n)). 3. f1 (n) + f2 (n) = O(max(g1(n)); g2(n))) y (min(h1 (n); h2(n))). 4. f1 (n)f2 (n) = O(g1(n))g2(n)) y (h1 (n)h2(n)). 5. f1 (n)=f2(n) = O(g1(n))=h2(n)) y...