## 1.3.1 MÉTODO DE SUSTITUCIÓN

Es el método más simple y sencillo. Se va evaluando la recurrencia para ciertos valores. Se deduce, a partir del comportamiento mostrado, una ecuación que represente el comportamiento de la recurrencia. Se demuestra que la ecuación, efectivamente, resuelve a la recurrencia.

Ejemplo

Considere la siguiente recurrencia:

T(n)= 1 si n=1 y

3T(n/2) + n si n>1

¿Cómo resolverla?

Primera idea, construir una tabulación de los valores que toma la recurrencia para diferentes valores de n. La recurrencia solo queda definida para n potencias de 2, es decir, para n = 2k, donde k es un entero positivo.

n | T(n)
21 | 3T(1)+2 = 3x1+2
22 | 3T(2)+22 = 3[3x1+2]+22 = 32x1 + 3x2 + 22
23 | 3T(4)+23 = 3[32x1 + 3x2 + 22] + 23 = 33x1 + 32x2 + 31x22 + 23
24 | 3T(8)+24 = 3[33x1 + 32x2 + 31x22 + 23]+24 = 34x1+33x2+32x22+3x23+24

Por tanto: T(2k) = 3k+1-2k+1

Como sabemos que n = 2k -> log2n = k, con lo cual se obtiene una T en términos de n: T(n) = 3log n +1 – 2log n +1

Características

- Consta de 2 pasos:
  - Adivinar la forma de la solución.
  - Utilizar inducción matemática para encontrar las constantes y mostrar que la solución funciona.
- Método poderoso.
- Solo se aplica a casos en que es fácil adivinar la forma de la respuesta.
- Se usa para establecer fronteras superiores o inferiores en una recurrencia.
- No hay una buena manera general de adivinar soluciones correctas a recurrencias.
  - Requiere experiencia y creatividad.
  - Algunas heurísticas
    - Usar árboles de recursión para generar buenos valores iniciales.
    - Si la recurrencia es similar a otra, usar una solución similar.

###