No tengo tiempo suficiente para resolver estas recurrencias, pero le señalaré los tres métodos que se presentan en Introducción a los algoritmos: “maestro”, árboles de recursión y sustitución.
En ningún orden particular:
Puede dibujar un árbol de recursión para medir la cantidad de tiempo de ejecución. La idea es dibujar un nivel y luego ramificarse al siguiente nivel. Por ejemplo, para el algoritmo 2, en el primer “nivel”, tendrá n lg n + 100 lg n.
En el siguiente, debido a la naturaleza del algoritmo, tendrá un conjunto de 4 * (T (n / 2)) o 4 * (n / 2 * lg n / 2 + 100 lg n / 2). La idea es encontrar el patrón y sumar todos los tiempos de ejecución. Un bonito gráfico:
- Cómo demostrar que este gráfico todavía puede estar fuertemente conectado
- Cómo obtener el vértice extremo de un gráfico
- ¿Cómo encontrar una ruta con la suma máxima en un BST (no BT)?
- ¿Son los algoritmos de big data de caja negra una instancia de historia que se repite? ¿Qué está haciendo la comunidad de código abierto para crear algoritmos de big data transparentes y precisos?
- ¿Cómo puedo ser bueno en algoritmos si soy débil en matemáticas?
Los otros dos métodos son más teóricos. El método de sustitución es una forma de inducción que implica confirmar una solución conocida, adivinada o supuesta al problema. En la prueba a continuación, se supone que T (n) es n ^ 2, y se confirma. 
El último método consiste en resolver las recurrencias de la forma T (n) = aT (n / b) + f (n) con dos constantes positivas conocidas a y b, y un tiempo de ejecución de f (n). Este método se explica en el siguiente extracto:
Recuerde que algunas recurrencias, como el Algoritmo 1, que no tiene la forma aT (n / b) + f (n). En los otros casos, la función adicional se puede simplificar a alguna forma de O (como en el Algoritmo 3, donde 2n – 4 = O (n).
