Page 218 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Nótese que en los tres casos no se cubren todas las posibilidades para f (n). Existe un vacío entre los
casos 1 y 2 cuando f (n) es menor que pero no polinomialmente menor. Similarmente, existe
un vacío entre los casos 2 y 3 cuando f (n) es mayor que , pero no polinomialmente mayor.

Si la función f (n) 9 cae en uno de esos vacíos, o si la condición de regularidad en el caso 3 no se
cumple, entonces no se puede usar el método maestro para resolver la recurrencia. Para emplear el
método maestro, solo hay que determinar en qué caso cae la recurrencia.

Por ejemplo, considérese la recurrencia Tenemos que a= 9, b = 3 y f (n)
=n; de aquí que Dado f (n) = 0 ( n ), y proponiendo que = 9, entonces
2-n
se puede ver que se cumple que f (n) = 0 (n ), por lo que se aplica el caso 1 y se concluye que la
1.1
solución es T (n)= 0 (n )
2
Considérese la recurrencia entonces se tiene de
esta forma por lo tanto, n° =1. Se puede ver que se cumple que 1 = 0 (1), por lo
que se aplica el caso 2 y finalmente la solución de la recurrencia es

Ahora véase la siguiente recurrencia: se tiene que de
n= esta forma Dado que si tomamos aplica el
caso 3 si se puede demostrar la condición de regularidad de .f (n) Para un suficientemente grande,
tenemos que 2(n/4) < cn; reduciendo términos, se concluye que la condición de regularidad se cum-
ple para 1/2 < c < 1. Por lo tanto, T(n) = 0(n).

ejercicios

Resuelva los ítems empleando cualquier método.

212