Trois récurrences, trois régimes

On déroule sur ${\log }_{2}n$ étages, en comptant le travail à chaque étage. À l'étage $j$, il y a $a^j$ sous-problèmes de taille $n/2^j$.

(a) $T(n)=2T(n/2)+n$. Étage $j$ : $2^j$ sous-problèmes coûtant $n/2^j$ chacun, soit $n$ par étage. Avec ${\log }_{2}n+1$ étages : $T(n)=n({\log }_{2}n+1)=\Theta (n\log n)$. Tous les étages pèsent pareil.

(b) $T(n)=4T(n/2)+n$. Étage $j$ : $4^j\cdot n/2^j=2^{j}n$. La somme géométrique est dominée par son dernier terme : $T(n)={\sum }_j{2}^{j}n=\Theta (n\cdot 2^{{\log }_{2}n})=\Theta (n^2)$. Les feuilles dominent.

(c) $T(n)=2T(n/2)+n^2$. Étage $j$ : $2^j(n/2^j{)}^2=n^2/2^j$. La somme est dominée par son premier terme : $T(n)=n^2{\sum }_j{2}^{-j}=\Theta (n^2)$. La racine domine.

La vérification numérique, en déroulant les récurrences à $n=1024$ :

Ce qu'il faut remarquer, et c'est le point de l'exercice. Les lignes (b) et (c) donnent exactement la même valeur $2n^2-n$, et pourtant elles ne se ressemblent en rien : dans (b) le travail est presque entièrement dans les $n^2$ feuilles, dans (c) il est presque entièrement dans l'appel initial. Une même complexité peut recouvrir deux comportements opposés — et cela se voit dès qu'on change autre chose : si l'on paralléliseait, (c) ne gagnerait rien et (b) tout.

La ligne $3T(n/2)+n$ est celle de Karatsuba (exercice suivant) : $n^{{\log }_{2}3}=n^{1,585}$, et $175099\approx 2,96\times 1024^{1,585}$.

La règle pratique. Comparer $a$ à $b^{\mathrm{deg}f}$ : si $a<b^{\mathrm{deg}f}$ la racine domine, si $a>b^{\mathrm{deg}f}$ les feuilles dominent, si $a=b^{\mathrm{deg}f}$ tous les étages pèsent pareil et un $\log$ apparaît. C'est le calcul du chapitre chap:recursivite, à faire à la main chaque fois.