Problème — $T(n)=aT(n/2)+f(n)$ : trois régimes, résolus à la main

Posons $n=2^k$. L'arbre des appels a $k+1$ niveaux, et le niveau $j$ compte $a^j$ appels portant chacun sur $n/2^j$ éléments.

1. Coût constant par appel. Le niveau $j$ coûte $a^{j}b$, et le total est la somme géométrique $b{\sum }_{j=0}^k{a}^j$.

• $a=1$ : $T(n)=b(k+1)=\Theta (\log n)$.
• $a=2$ : $T(n)=b(2^{k+1}-1)=b(2n-1)=\Theta (n)$.
• $a=3$ : $T(n)=b\frac{3^{k+1}-1}{2}=\Theta (3^{{\log }_{2}n})=\Theta (n^{{\log }_{2}3})=\Theta (n^{1,585})$, car $3^{{\log }_{2}n}=n^{{\log }_{2}3}$.

Mesuré, en comptant les nœuds de l'arbre :

n = 1024 : a=1 -> 11 noeuds   a=2 -> 2047 noeuds    a=3 -> 88573 noeuds
n = 4096 : a=1 -> 13 noeuds   a=2 -> 8191 noeuds    a=3 -> 797161 noeuds
verification : k+1 = 11 ; 2n-1 = 2047 ; (3^11-1)/2 = 88573

2. Coût linéaire par appel. Le niveau $j$ coûte $a^j\times cn/2^j=cn(a/2{)}^j$. Tout tient dans la raison $a/2$.

• $a=1$, raison $1/2<1$ : la somme converge, $T(n)=cn\sum (1/2{)}^j<2cn=\Theta (n)$. La racine domine.
• $a=2$, raison $1$ : tous les niveaux coûtent $cn$, il y en a $k+1$, donc $T(n)=\Theta (n\log n)$. Tous les niveaux pèsent pareil.
• $a=3$, raison $3/2>1$ : la somme est dominée par son dernier terme, $T(n)=\Theta (n(3/2{)}^k)=\Theta (n^{{\log }_{2}3})$. Les feuilles dominent.

Mesuré :

n = 1024 : a=1 -> 2047     a=2 -> 11264      a=3 -> 175099
verification : 2n-1 = 2047 ; n(log2 n + 1) = 1024 x 11 = 11264

Ce que ces six calculs montrent, et c'est la raison de la consigne du programme : il n'y a rien à retenir d'autre que la raison de la suite géométrique des coûts par niveau. Si elle est $<1$, la racine paie tout ; si elle vaut $1$, on multiplie par le nombre de niveaux ; si elle est $>1$, les feuilles paient tout. Un théorème-maître ne dit rien de plus, et il masque ce qui se voit ici en trois lignes.

3. Les algorithmes.

• $a=1$, $f=b$ : recherche dichotomique, $\Theta (\log n)$ — exercice plus haut.
• $a=2$, $f=b$ : parcours d'un arbre binaire complet, $\Theta (n)$ — chapitre chap:arbres.
• $a=2$, $f=cn$ : tri par partition-fusion, $\Theta (n\log n)$ — problème précédent.
• $a=1$, $f=cn$ : recherche du $k$-ième plus petit par partition, $\Theta (n)$ — chapitre chap:diviser.
• $a=3$, $f=cn$ : multiplication de Karatsuba, $\Theta (n^{{\log }_{2}3})$ — chapitre chap:diviser. C'est le cas qui justifie l'astuce : passer de quatre à trois multiplications de demi-tailles fait tomber l'exposant de $2$ à $1,585$.