Soit T(n) la complexité dans le pire des cas de l'algorithme appliqué à un problème de taille n. 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 d(n). Enfin, on se donne la complexité T(1) 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 n est une puissance de b ; 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 a et 
.
, cette somme vaut 
;
donc 
. Ainsi, si 
et a=b (cas très usuel, en particulier de la FFT, du tri par fusion
et du tri rapide), on a 
. Si 
et a=1 (cas de la recherche dichotomique), on
obtient 
.
,
, le terme dominant est 
, qui est
indépendant de 
et qui est du même ordre que le premier terme,
donc 
. Ainsi, si et a>b (cas
de la multiplication matricielle de Strassen, où a=7 et b=2), on a
.
, le terme dominant est 
, donc
. La décomposition du problème ne conduit
dans ce dernier cas à aucune accélération, les opérations de
décomposition et recomposition étant dominantes. C'est le cas de
l'équation 
.