Résoudre les récurrences

Cette séance de cours couvre l'analyse des algorithmes de tri tels que le tri par insertion et le tri par fusion, en mettant l'accent sur le réarrangement des nombres en place dans les tableaux. Il se penche également sur l'analyse des algorithmes de division et de conquête, en se concentrant spécifiquement sur Merge Sort. La séance de cours progresse ensuite vers la résolution des récidives par induction, en discutant des limites supérieures et inférieures avec des preuves. En outre, il aborde les complexités introduites par les planchers et les plafonds dans les relations de récurrence et les erreurs courantes dans lutilisation de la méthode de substitution. La méthode Master est introduite comme un outil pour résoudre les récurrences d'une forme spécifique.