Dans un algorithme itératif, le décompte du nombre d'opérations élémentaires se fait en additionnant le nombre d'opérations de chaque itération. C'est pourquoi dans le chapitre précédent nous avons souvent utilisé des calculs de sommes pour arriver à nos fins.

La complexité d’un algorithme récursif traitant des données d'une certaine taille va quand à elle naturellement dépendre de la complexité du même algorithme avec des données de taille inférieure. Cette complexité va donc être une suite définie par récurrence.

Dans la suite de cette partie on se limitera au cas des suites arithmético-géométriques et des suites récurrentes linéaires d’ordre $2$. Cela sera déjà bien suffisant pour calculer la complexité de nombreux algorithmes récursifs.

Commençons par une définition, sans doute déjà connue du lecteur.

On prend l'habitude de distinguer deux cas particuliers, celui des suites arithmétiques et celui des suites géométriques.

Le résultat suivant nous donne l'expression explicite du terme général d'une suite arithmético-géométrique.

	On admettra ce résultat, ce n’est pas l’objet de ce cours. Ce n’est ceci-dit pas bien méchant à démontrer.

Nous utiliserons peu cette expression exacte, mais plutôt l'approximation suivante qui nous renseigne sur l'ordre de grandeur du terme général d'une suite arithmético-géométrique.

	La restriction que $a$, $b$ et $u_0$ soient positifs n'est absolument pas génante car ça sera toujours le cas dans notre contexte de calculs de complexité.

Voyons maintenant sur des exemples comment appliquer ce qui précède. Le premier concerne la très fameuse fonction factorielle.

def factorielleRecursive(n):
    if n == 0:
        return 1
    else:
        return n*factorielleRecursive(n-1)

	A noter que l'algorithme itératif calculant cette factorielle a la même complexité. Le voici en effet en Python : def factorielleIterative(n): resultat = 1 for i in range(2,n+1): resultat *= i return resultat On a une structure for qui réalise $n-1$ itérations, chacune comportant le même nombre fixe d'opérations élémentaires. C'est pourquoi là aussi $T\left(n\right)=\Theta \left(n\right)$.

L'exemple suivant est le fameux problème des tours de Hanoï, imaginé par le mathématicien français Edouard Lucas (1842-1891).

	Ce problème a été recontré dans les séances d'exercices du cours 1ADS mais nous allons le redétailler.

Example 1.2. Problème des tours de Hanoï

Le but est de déplacer $n$ disques de diamètres différents, d’une tour initiale (celle de gauche) à une tour finale (celle de droite) en passant par une tour intermédiaire (celle du milieu).

Initialement, tous les disques sont empilés sur la tour initiale, du plus grand au plus petit.

Les règles de déplacement sont les suivantes :

• On ne peut bouger qu’un seul disque à la fois.

• On ne peut déplacer un disque que vers une tour vide, ou sur un disque plus grand.

Etudions "à la main" le cas $n=3$.

Voici la position initiale :

Effectuons ces trois premiers mouvements :

On a donc réussi à bouger les deux plus petits disques vers la tour intermédiaire en passant par la tour finale.

Bougeons maintenant le plus grand :

Il ne reste plus qu'à effectuer ces trois derniers mouvements qui ressemblent évidemment fortement aux trois premiers :

Et le problème est résolu pour trois disques.

Essayons maintenant de reproduire dans le cas général ce que l'on vient de faire dans ce cas très particulier. On arrive vite à la conclusion que la résolution du problème pour toute valeur de $n$ est récursive :

• On déplace $n-1$ disques de la tour initiale à la tour intermédiaire en passant par la tour finale.

• On déplace le plus grand disque de la tour initiale vers la tour finale.

• On déplace $n-1$ disques de la tour intermédiaire à la tour finale en passant par la tour initiale.

Le cas de base étant le déplacement d'un seul disque.

En Python cela donne cette implémentation :

def hanoi(de,vers,via,n):
    if n==1:
        print(de," vers ",vers)
    else:
        hanoi(de,via,vers,n-1)
        print(de," vers ",vers)
        hanoi(via,vers,de,n-1)


hanoi("1","3","2",3)

Sans surprises, pour trois disques on retrouve bien les mouvements précédemment mis en images :

1  vers  3
1  vers  2
3  vers  2
1  vers  3
2  vers  1
2  vers  3
1  vers  3

Venons-en maintenant au calcul de la complexité de cette procédure qui n'est composée que d'une structure conditionnelle.

Si $n>1$, une opération élémentaire (une comparaison) est effectuée lors du test, une autre lors de l'affichage, et on a deux appels récursifs. On a ainsi $T\left(n\right)=2T\left(n-1\right)+2$.

Si $n=1$, seule la comparaison a lieu donc $T\left(1\right)=1$.

La complexité $T$ est donc une suite arithmético-géométrique associée aux constantes $a=2$ et $b=2$.

D’après le résultat précédent, on a alors $T\left(n\right)=\Theta \left(2^n\right)$. Cet algorithme est donc de complexité exponentielle.

Cette sous-partie n'est pas conceptuellement très difficile, mais elle demande de la vigilance car certains résultats sont assez techniques.

On distinguera le cas des suites homogènes des suites non homogènes, et l'on verra qu'en pratique ce sont ces dernières qui nous intéresserons le plus.

 Suites homogènes

Commençons naturellement par une définition du concept.

Définition

Une suite réelle ${\left({}_n\right)}_{n\in N}$ est une suite récurrente linéaire homogène d'ordre deux s'il existe deux réels $a$ et $b$ tels que

$\forall n\ge 2,u_n=a{u}_{n-1}+b{u}_{n-2}$

Pour étudier une telle suite, on doit tout d'abord lui associer un polynôme dit caractéristique.

Définition

Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire homogène d'ordre deux associée aux réels $a$ et $b$.

Le polynôme caractéristique de la suite ${\left({}_n\right)}_{n\in N}$ est par définition le polynôme $x^2-ax-b$.

L'équation caractéristique de la suite ${\left({}_n\right)}_{n\in N}$ est alors l'équation $x^2-ax-b=0$.

Le terme général d'une suite récurrente linéaire homogène d'ordre deux va alors s'exprimer en fonction des racines de son polynôme caractéristique.

	On ne fera pas l'insulte au lecteur de lui rappeler comment l'on calcule les racines d'un polynôme du second degré.

Propriété

Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire homogène d'ordre deux et soit $\Delta$ le discriminant de son équation caractéristique.

Si $\Delta >0$, en notant $x_1$ et $x_2$ les deux racines réelles distinctes du polynôme caractéristique, on a

$\exists \lambda ,\mu \in R,\forall n\in N,u_n=\lambda x_1^n+\mu x_2^n$

Si $\Delta =0$, en notant $x$ la racine réelle double du polynôme caractéristique, on a

$\exists \lambda ,\mu \in R,\forall n\in N,u_n=\left(\lambda n+\mu \right)x^n$

Dans les deux cas, les constantes $\lambda$ et $\mu$ se déterminent à l’aide de la valeur des deux premiers termes de la suite. On a alors un système linéaire de deux équations à deux inconnues à résoudre.

	On ne traitera pas le cas où $\Delta <0$ car on ne le rencontrera pas lors de nos calculs de complexités. En un mot, on peut alors montrer que les suites sont alors exprimables à l’aide des fonctions cosinus et sinus. Ou au choix de l’exponentielle complexe.

Appliquons ce resultat sur un exemple célèbre, la suite due au mathématicien italien Leonardo Fibonacci (1175-1250).

Example 1.3. Suite de Fibonacci

La suite de Fibonnaci est la suite récurrente linéaire homogène d'ordre deux définie par

$u_n=\{\begin{array}{cc}0& \text{si}n=0\\ 1& \text{si}n=1\\ u_{n-1}+u_{n-2}& \text{si}n\ge 2\end{array}$

L'équation caractéristique de cette suite est $x^2-x-1=0$. Son discriminant $\Delta$ est égal à $5$. Le polynôme caractéristique possède donc deux racines distinctes $x_1=\frac{1+\sqrt{5}}{2}$ et $x_2=\frac{1-\sqrt{5}}{2}$.

D'après le résultat précédent

$\exists \lambda ,\mu \in R,\forall n\in N,u_n=\lambda {\left(\frac{1+\sqrt{5}}{2}\right)}^n+\mu {\left(\frac{1-\sqrt{5}}{2}\right)}^n$

On détermine alors $\lambda$ et $\mu$ en se servant de la valeur des deux premiers termes $u_0$ et $u_1$.

On a en effet d'une part $u_0=0$ et $u_1=1$ d'après la définition de la suite, et d'autre part d'après l'expression du terme général

$\{\begin{array}{c}{u}_0=\lambda +\mu \\ u_1=\lambda \left(\frac{1+\sqrt{5}}{2}\right)+\mu \left(\frac{1-\sqrt{5}}{2}\right)\end{array}$

On doit donc résoudre le système

$\{\begin{array}{c}0=\lambda +\mu \\ 1=\lambda \left(\frac{1+\sqrt{5}}{2}\right)+\mu \left(\frac{1-\sqrt{5}}{2}\right)\end{array}$

On trouve $\lambda =\frac{1}{\sqrt{5}}$ et $\mu =-\frac{1}{\sqrt{5}}$. Finalement, on obtient

$\forall n\in N,u_n=\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^n$

Rappelons maintenant un résultat classique sur les limites, qui nous permettra ensuite d'obtenir l'ordre de grandeur d'une suite récurrente linéaire.

Propriété

Soit $x$ élément de $R$.

On a

• Si $x>1$, $\underset{n\to \infty }{lim}{x}^n=+\infty$.

• Si $-1<x<1$, $\underset{n\to \infty }{lim}{x}^n=0$.

• Si $x\le -1$, $x^n$ n'a pas de limite quand $n\to +\infty$.

Le prochain résultat sera celui qui in fine nous servira lors de nos calculs de complexité.

Propriété

Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire homogène d'ordre deux et soit $\Delta$ le discriminant de son équation caractéristique.

On suppose que $\Delta >0$ et l'on note $x_1$ et $x_2$ les deux racines réelles distinctes du polynôme caractéristique.

Si $x_1>1$, et si $\left|x_1\right|>\left|x_2\right|$, alors $u_n=\Theta \left(x_1^n\right)$.

Cette propriété signifie moralement que sous certaines conditions $x_1^n$ impose le comportement asymptotique de la suite. Appliquons la à la suite de Fibonacci.

Example 1.4. Ordre de grandeur de la suite de Fibonacci

Pour la suite de Fibonacci, on a montré que $\Delta =5$, $x_1=\frac{1+\sqrt{5}}{2}$ et $x_2=\frac{1-\sqrt{5}}{2}$. Les hypothèses de la propriété précédente sont donc vérifiées. Ainsi $u_n=\Theta \left({\left(\frac{1+\sqrt{5}}{2}\right)}^n\right)$.

def fibonacci(n):
    if n<2:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Commençons par rappeler les trois étapes du paradigme "diviser pour régner" :

Avec ce paradigme, la complexité d’un algorithme traitant des données de taille $n$ va naturellement dépendre de la complexité du même algorithme avec des données de taille $n/b$, où $b$ est le facteur avec lequel on divise le problème en sous-problèmes.

Il va falloir de plus tenir compte de la complexité de l’étape de combinaison des résultats des sous-problèmes.

Avant le cas général, nous allons commencer par étudier un exemple, celui du tri fusion.

Le tri fusion consiste à trier récursivement les deux moitiés de la liste, puis à fusionner ces deux sous-listes triées en une seule. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car une telle liste est évidemment déjà triée.

	Nous renvoyons le lecteur à ce chapitre du cours 1ADS pour la description des principaux algorithmes de tri, y compris celui-ci.

Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme :

Example 1.6. Déroulement du tri fusion sur un exemple

On considère la liste suivante de sept entiers :

On la scinde en deux sous-listes en la coupant par la moitié :

Sous-listes que l’on scinde à leur tour :

Sous-listes que l’on scinde à leur tour :

Ces sous-listes sont triées car elles n’ont qu’un élément. On va maintenant les fusionner deux par deux en de nouvelles sous-listes triées :

De nouveau une étape de fusionnnement :

Une dernière fusion :

On a fusionné toutes les sous-listes obtenues lors des appels récursifs, le tri est terminé :

En voici son implémentation en Python :

def fusion(l,first,middle,last):
    i,j = first,middle+1
    pro = []
    while (i<=middle) and (j<=last):
        if l[i]<=l[j]:
            pro.append(l[i])
            i+=1
        else:
            pro.append(l[j])
            j+=1
    while i<=middle:
        pro.append(l[i])
        i+=1
    while j<=last:
        pro.append(l[j])
        j+=1
    for k in range(last-first+1):
        l[first+k] = pro[k]

def triFusionRec(l,first,last):
    if first<last:
        triFusionRec(l,first,(first+last)//2)
        triFusionRec(l,((first+last)//2)+1,last)
        fusion(l,first,(first+last)//2,last)

def triFusion(l):
    triFusionRec(l,0,len(l)-1)

	Bien prendre le temps d'appréhender le fonctionnement de cet algorithme.

Voici maintenant le résultat établissant la complexité du tri fusion. Vu la nature même de celui-ci, le lecteur comprendra facilement qu'il n'y a pas de meilleur ou pire des cas.

L'idée pour démontrer ce résultat est de construire l'arbre des appels récursifs, d'évaluer le coût de chaque sommet, puis d'en faire la somme.

Démonstration

Commençons par remarquer que la procédure de fusion est de complexité linéaire. Plus précisément, pour fusionner deux tableaux de taille $n/2$, on a une complexité en $\Theta \left(n\right)$. Dans l’algorithme précédent $n$ étant la différence entre "last" et "first" et donc $n/2$ la différence entre "middle" et "first" ou "last" et "middle". Cela provient du fait que l'on traite une et une seule fois chaque élément des deux listes à fusionner, et que ce traitement est de complexité constante.

Dans la suite de cette preuve on va supposer que $n$ est une puissance de $2$, cela nous permettra d'avoir des subdivisions qui "tombent juste".

A chaque appel récursif, on subdivise un problème de taille $n$ en $2$ sous-problèmes de taille $n/2$, les $2$ sous-listes que l'on va trier récursivement. A un niveau $j$ on aura donc $2^j$ sous-problèmes. Chacun de ces sous-problèmes sera de taille $n/2^j$, et aura ainsi un coût de l'ordre de $n/2^j$ (rappelons que la procédure de fusion est de complexité linéaire).

Le coût d'un niveau $j$ est donc $2^j\times \left(\frac{n}{2^j}\right)=n$. C'est en effet le nombre de sous-problèmes du niveau $j$ multiplié par le coût de chacun d'eux.

Pour mieux visualiser tout cela, voici l'arbre des appels récursifs, sur chaque sommet étant indiqué la taille du paramètre lors de l'appel en question :

On a supposé que $n$ était une puissance de $2$, donc $n$ est de la forme $n=2^h$ où $h$ est la hauteur de l'arbre. C'est pourquoi $h=\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)$. Egalité que l'on a utilisée dans la figure précédente.

Le nombre de niveaux est alors égal à $h+1$ (ne pas oublier le niveau initial), i.e. $\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)+1$. On a de plus déjà constaté que le coût de chaque niveau était égal à $n$.

Le coût total est alors égal à la somme des coûts de tous les niveaux, i.e. $\mathrm{n}\times \left(\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)+1\right)$. Q.E.D.

Dans la preuve précédente, on a supposé que $n$ était une puissance de $2$, ce qui a facilité notre étude de l'arbre. Si ce n'est pas le cas, il faut alors l'encadrer entre deux puissances de $2$, puis effectuer le raisonnement précédent sur ces deux puissances. On arrive alors relativement facilement au résultat. Nous ne rentrerons pas dans ces détails car ils n'apportent rien en terme de compréhension profonde.

Dans cette sous-partie nous n'allons plus nous limiter au cas du tri fusion, mais nous allons présenter et démontrer un résultat applicable à la majorité des algorithmes de type diviser pour régner.

Nous allons donc nous intéresser à des algorithmes de la forme :

def divideAndConquer(n):
    if n ==1:
        end of processing
    else:
        divideAndConquer(n//b)
        divideAndConquer(n//b)
        ... a times
        divideAndConquer(n//b)
        work of cost f(n) for dividing the problem
            and merging the solutions to
            the subproblems

Un problème de taille $n$ est ainsi divisé en $a$ sous-problèmes de taille $n/b$, avec un coût $f\left(n\right)$ pour combiner les résultats de ces sous-problèmes.

	Il est donc implicitement supposé que chaque sous-problème a la même taille. Dans le cas contraire le Master Theorem ne peut s'appliquer.

	Il n’est pas nécessaire de préciser la base du logarithme dans le deuxième cas, puisque rappelons le toutes les fonctions logarithmes diffèrent juste d’une constante multiplicative.

Comme lors de la démonstration de la complexité du tri fusion, nous allons étudier l'arbre des appels récursifs en faisant la somme des coûts de chaque sommet. Certains arguments seront donc similaires à ceux utilisés dans la sous-partie précédente.

Nous aurons également besoin du petit lemme suivant :

Démonstration du Master Theorem

Dans la suite de cette preuve on va supposer que $n$ est une puissance de $b$, cela nous permettra d'avoir des subdivisions qui "tombent juste".

A chaque appel récursif, on subdivise un problème de taille $n$ en $a$ sous-problèmes de taille $n/b$. A un niveau $j$ on aura donc $a^j$ sous-problèmes. Chacun de ces sous-problèmes sera de taille $n/b^j$, et aura ainsi un coût de l'ordre de ${(n/{}^{})}^d$ (rappelons que la complexité de la procédure de combinaison est en $\Theta \left(n^d\right)$).

Le coût d'un niveau $j$ est donc $a^j\times {\left(\frac{n}{{}^{}}\right)}^d$. C'est en effet le nombre de sous-problèmes du niveau $j$ multiplié par le coût de chacun d'eux.

Pour mieux visualiser tout cela, voici l'arbre des appels récursifs, sur chaque sommet étant indiqué la taille du paramètre lors de l'appel en question :

On a supposé que $n$ était une puissance de $b$, donc $n$ est de la forme $n=b^h$ où $h$ est la hauteur de l'arbre. C'est pourquoi $h=\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)$. Egalité que l'on a utilisée dans la figure précédente.

Contrairement au tri fusion, chaque niveau n'a pas le même coût, et l'on ne peut donc avoir le coût total en multipliant le nombre de niveaux par le coût de chacun d'eux.

Pour estimer $T\left(n\right)$ on doit ainsi calculer la somme

$\sum _{j=0}^{lo{g}_b\left(n\right)}{a}^j\times {\left(\frac{n}{{}^{}}\right)}^d$

On peut factoriser par $n^d$ dans cette somme puisque ce terme ne dépend pas de l'indice $j$ de sommation. On obtient alors l'égalité

$\sum _{j=0}^{lo{g}_b\left(n\right)}{a}^j\times {\left(\frac{n}{{}^{}}\right)}^d=n^d\sum _{j=0}^{lo{g}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j$

On reconnaît la somme des premiers termes d'une suite géométrique de raison $q=\frac{a}{b^d}$. La valeur de cette quantité va donc déterminer celle de la complexité totale. Plus précisément, on devra distinguer les cas où $\frac{a}{b^d}$ est plus petit, plus grand ou égal à $1$.

Cas où $a=b^d$ :

On a alors $\frac{a}{b^d}=1$, et l'on est ramené à une somme de termes constants

$\begin{array}{ccc}{n}^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j& =& n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}1\\ & =& n^d\times \left(\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)+1\right)\end{array}$

D'où

$T\left(n\right)=\Theta \left(n^d\mathrm{l}\mathrm{o}\mathrm{g}\left(n\right)\right)$

Cas où $a<b^d$ :

On utilise la première inégalité du lemme pour obtenir

$n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j\le n^d\frac{1}{1-\frac{a}{b^d}}$

D'où

$T\left(n\right)=\Theta \left(n^d\right)$

Cas où $a>b^d$ :

On utilise cette fois la seconde inégalité du lemme. Il vient

$n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j\le n^d{\left(\frac{a}{{}^{}}\right)}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}\left(1+\frac{1}{\frac{a}{b^d}-1}\right)$

Quelques changements d'expressions dues aux règles opératoires usuelles sur les puissances conduisent à

$\frac{n^d}{b^{d\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}}=n^d{b}^{-d\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}=n^d{\left({}^{}\right)}^{-d}$

Or l'on sait que les fonctions logarithmes et exponentielles de base $b$ sont réciproques l'une de l'autre. Cela implique en particulier que $b^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}=n$

On a alors

$n^d{\left({}^{}\right)}^{-d}=n^d{n}^{-d}=1$

Cela prouve que

$n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j\le a^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}\left(1+\frac{1}{\frac{a}{b^d}-1}\right)$

Et donc

$T\left(n\right)=\Theta \left(a^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}\right)$

Il ne reste plus qu'à constater que $a^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}=n^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)}$. Cela est vrai car les logarithmes dans la base $b$ de chacun de ces deux termes sont égaux à $\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)\times \mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)$.

	Si $n$ n'est pas une puissance de $b$ il faut procéder par encadrement. Comme pour le tri fusion nous ne rentrerons pas dans ces détails.

Pour terminer cette sous-partie, on propose au lecteur un petit exercice corrigé afin qu'il s'interroge sur les conditions d'application du Master Theorem.

	Si l'on se retrouve dans une situation où le Master Theorem ne s'applique pas, il faut considérer l'arbre des appels récursifs et l'analyser en détail. Un peu comme dans la preuve du théorème, mais en prenant bien sûr en compte les facteurs qui ont fait qu'il ne s'appliquait pas.

Livrons nous maintenant à une petite interprétation de chacun des cas du Master Theorem afin de mieux en comprendre leur essence.

Rappelons que le coût d'un niveau $j$ est proportionnel à $a^j\times {\left(\frac{n}{{}^{}}\right)}^d$, quantité que l'on peut mettre sous la forme $n^d\times {\left(\frac{a}{{}^{}}\right)}^j$.

La constante $a$ peut être vue comme la vitesse de prolifération des sous-problèmes, et le terme $b^d$ comme la vitesse de diminition du coût de traitement par sous-problème.

Le fait que l'une de ces vitesses prenne le pas sur l'autre ou au contraire qu'elles se compensent expliquera la complexité finale.

Voici les trois situations possibles :

Les notations et leur signification seront les mêmes que dans la version dite simple, mais les hypothèses seront moins restrictives, en particulier celles portant sur la complexité de la procédure de subdivision et combinaison.

Nous présentons cette version du théorème par soucis de complétude, mais en général la précédente suffit. D'ailleurs nous n'en ferons pas de démonstration, les "nouveaux" arguments étant essentiellement mathématiques.

	On trouve ce théorème sous cette forme générale dans l'excellent livre de Thomas H. Cormen (1956-), Charles E. Leiserson (1953-), Ronald L. Rivest (1947-) et Clifford Stein (1965-), "Introduction to algorithms". Ne pas se fier au titre, ce livre est bien plus qu'une introduction, c'est une référence.