Récurrences

On note $h={\log }_{2}n$ le nombre de niveaux de l'arbre des appels.

• Un seul appel par niveau, sur une taille divisée par $2$ : les niveaux coûtent $\alpha n$, $\alpha n/2$, $\alpha n/4$, … Leur somme est inférieure à $2\alpha n$ (série géométrique), d'où $t(n)\in \Theta (n)$ : le premier niveau domine.
• Le niveau $p$ compte $3^p$ appels de taille $n/2^p$ : il coûte $\alpha n(3/2{)}^p$. La somme géométrique de raison $3/2>1$ est dominée par son dernier terme, $\alpha n(3/2{)}^h=\alpha 3^h=\alpha n^{{\log }_{2}3}$. Les $3^h=n^{{\log }_{2}3}$ feuilles coûtent $\beta n^{{\log }_{2}3}$. Donc $t(n)\in \Theta (n^{{\log }_{2}3})$, avec ${\log }_{2}3\approx 1,585$ : c'est la complexité de l'algorithme de Karatsuba (chapitre 13).
• Le niveau $p$ coûte $\alpha n{2}^p$ ; la somme est dominée par les $4^h=n^2$ feuilles : $t(n)\in \Theta (n^2)$. Découper en deux moitiés ne sert à rien si l'on fait quatre appels récursifs.