De nombreux algorithmes sont récursifs. Lorsque nous les analysons, nous obtenons une relation de récurrence pour la complexité temporelle. Nous obtenons le temps d'exécution sur une entrée de taille n en fonction de n et le temps d'exécution sur des entrées de plus petites tailles. Par exemple, dans Merge Sort , pour trier un tableau donné, nous le divisons en deux moitiés et répétons récursivement le processus pour les deux moitiés. Enfin, nous fusionnons les résultats. La complexité temporelle du tri par fusion peut être écrite sous la forme T = 2T(n/2) + cn. Il existe de nombreux autres algorithmes comme la recherche binaire, la tour de Hanoï, etc. 

Il existe principalement trois façons de résoudre les récurrences. 

1) Méthode de substitution : Nous faisons une supposition pour la solution, puis nous utilisons l'induction mathématique pour prouver que la supposition est correcte ou incorrecte.

Par exemple, considérons la récurrence T(n) = 2T(n/2) + n

Nous devinons la solution comme T(n) = O(nLogn). On utilise maintenant l'induction
pour prouver notre conjecture.

Nous devons prouver que T(n) <= cnLogn. On peut supposer que c'est vrai
pour des valeurs inférieures à n.

T(n) = 2T(n/2) + n
    <= 2cn/2Log(n/2) + n
    = cnLogn - cnLog2 + n
    = cnLogn - cn + n
    <= cnLogn

2) Méthode de l'arbre de récurrence : dans cette méthode, nous dessinons un arbre de récurrence 
et calculons le temps pris par chaque niveau de l'arbre. Enfin, nous résumons le travail effectué 
à tous les niveaux. Pour dessiner l'arbre de récurrence, nous partons de la récurrence donnée et 
continuons à dessiner jusqu'à ce que nous trouvions un modèle parmi les niveaux. Le motif est généralement 
une série arithmétique ou géométrique. 

Pour connaître la valeur de T(n), il faut calculer la somme de tree
nœuds niveau par niveau. Si nous additionnons l'arbre ci-dessus niveau par niveau,
on obtient la série suivante
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....
La série ci-dessus est une progression géométrique avec un rapport de 5/16.

Pour obtenir une borne supérieure, nous pouvons additionner la série infinie.
Nous obtenons la somme sous la forme (n^2 )/(1 - 5/16) qui est O(n^2 )

3) Master Method : 
Master Method est un moyen direct d'obtenir la solution. 
La méthode maître ne fonctionne que pour le type de récurrences 
suivant ou pour les récurrences qui peuvent être transformées dans le type suivant. 

T(n) = aT(n/b) + f(n) où a >= 1 et b > 1

Il y a trois cas suivants : 
1. Si f = O(n c ) où c < Log b a alors T = Θ(n Log b a ) 

2. Si f = Θ(n c ) où c = Log b a alors T = Θ(n c Log n) 

3. Si f = Ω(n c ) où c > Log b a alors T = Θ(f)

Comment cela marche-t-il?  
La méthode maître est principalement dérivée de la méthode de l'arbre de récurrence. Si nous dessinons l'arbre de récurrence de T = aT(n/b) + f, nous pouvons voir que le travail effectué à la racine est f, et le travail effectué à toutes les feuilles est Θ(n^c ) où c est Logb(a). Et la hauteur de l'arbre de récurrence est Logb(n)

Dans la méthode de l'arbre de récurrence, nous calculons le travail total effectué. Si le travail effectué au niveau des feuilles est polynomialement supérieur, alors les feuilles sont la partie dominante, et notre résultat devient le travail effectué au niveau des feuilles (Cas 1). Si le travail effectué au niveau des feuilles et de la racine est asymptotiquement le même, alors notre résultat devient la hauteur multipliée par le travail effectué à n'importe quel niveau (cas 2). Si le travail effectué à la racine est asymptotiquement plus, alors notre résultat devient le travail effectué à la racine (cas 3). 

Exemples d'algorithmes standards dont la complexité temporelle peut être évaluée à l'aide du Master Method 
Merge Sort : T = 2T(n/2) + Θ. Il tombe dans le cas 2 car c vaut 1 et Log b a] vaut aussi 1. Donc la solution est Θ(n Logn) 

Recherche binaire : T = T(n/2) + Θ(1). Il tombe aussi dans le cas 2 car c vaut 0 et Log b a vaut aussi 0. Donc la solution est Θ(Logn) 

Remarques : 
1) Il n'est pas nécessaire qu'une récurrence de la forme T = aT(n/b) + f puisse être résolue à l'aide du théorème maître. Les trois cas donnés présentent des écarts entre eux. Par exemple, la récurrence T = 2T(n/2) + n/Logn ne peut pas être résolue à l'aide de la méthode maître. 

2) Le cas 2 peut être étendu pour f = Θ(n^c Log^k(n)) 
Si f = Θ(n^c Log^k(n)) pour une constante k >= 0 et c = Logb(a), alors T = Θ(n^c Log^k+1(n))