Solution du TD8 sur les algorithmes diviser pour régner et le Master Theorem

Étude d'un cas synthétique

Anatomie d'un algorithme diviser pour reigner

Attention, il y a une erreur dans l'analyse des boucles, qui ne change pas le résultat. La somme de 0 à n de j devrait être simplifiée en j+1, ce qui rend la suite des calculs plus fastidieuse, mais ne change pas l'ordre de grandeur du résultat, et donc l'analyse qui en découle.

Application directe sur des formules L'addition de la primaire La multiplication de la primaire Découper le problème Un premier diviser pour régner La multiplication de Karatsuba