Complexité

On détermine la complexité d'un programme itératif en comptant le nombre d'itérations. Lorsque deux boucles sont imbriquées, on est amené à compter pour chaque itération de la boucle principale le nombre d'itérations de la boucle imbriquée et à les additionner. Par exemple,

A l'itération $i$ de l'algorithme, la boucle imbriquée effectue $n - (i + 1) + 1 = n - i$ itérations. On détermine donc le nombre total d'itérations en sommant les $n - i$, donc avec

$$(n-1) + (n-2) + \ldots + (n - (n - 1))= \sum_{i = 1}^{n-1} (n... ...)(n-1 + n - (n-1))}{2} = \frac{(n-1)n}{2} \in \mathcal{O}(n^2)$$