13 Ejercicios Resueltos paso a paso sobre recursividad usando Teorema Maestro

-->
El teorema maestro proporciona una solución paso a paso para estudiar el comportamiento del tiempo de ejecución de algoritmos que cumplen las siguiente relación de recurrencia:

donde T(n) es el tiempo de ejecución, a ≥ 1 y b >1 son constantes ademas

• n es el tamaño de todo el problema.
• a es el número de partes en que se ha dividido el problema original para estudiarlo recursivamente.
• (n/b) tamaño de cada parte en que se ha dividido el problema, asumiendo el mismo tamaño para cada parte.
• f(n) es el costo de realizar las llamadas recursivas, incluye el trabajo de dividir el problema y volver a unir las subtotales para obtener la solución total. F(n)  es un función independiente de T(n) y no negativa.

La relación de recurrencia se analiza expandiendo iterativamente el tiempo de ejecución y sustituyéndose en la misma ecuación, para evitar esta expansión se puede determinar un límite asintótico usando la notación de Landau (O grande) usada comúnmente en el análisis algoritmos Divide y vencerás.
Es posible determinar tres tipos de casos asintóticos --> d = log_b(a):

Ejemplos Resueltos

Caso 1

T(n)= Θ(n^log_b^(a)) Si existe alguna constante ε > 0 tal que f(n) ∈ O(n^log_b^{(a) –}ᵋ) 

Caso 2
-->

T(n)= Θ(^{n log}_b^(a) log^k+1(n)) Si f(n) ∈ Θ(n ^log_b^(a) log^k(n) ) para cualquier constante k ≥ 0

Caso 3
-->

T(n)= Θ(f(n)) SI existe ε> 0 tal que f(n) ∈ Ω (n^log _b^{(a) + ε}) la segunda condición es que exista alguna constante c < 1 tal que para todo n≥ 1 se cumple que: af(n/b)≤ cf(n)

También te interesa: Ejemplos resueltos sobre analisis iterativo de la complejidad de algoritmos recursivos

Si tienes información adicional sobre este tema, tus comentarios o links de referencia serán bienvenidos.