Soit la complexité dans le pire des cas de l'algorithme appliqué à un problème de taille . On suppose que la complexité des opérations de décomposition du problème et de recomposition des solutions des sous-problèmes a une complexité en . Enfin, on se donne la complexité sur un problème de taille 1. La complexité de l'algorithme est donc déterminée par l'équation de récurrence suivante :
Résolvons ces équations quand est une puissance de ; dans ce cas l'équation s'écrit : Sa solution est Le premier terme, correspond à la complexité due à la résolution de tous les sous-problèmes ; le second terme est la complexité due à toutes les opérations de décomposition/recomposition.Examinons ce deuxième terme quand . On a
Discutons selon les valeurs relatives de et .