Pour un tableau de n éléments, quelle est la complexité temporelle d'un traitement qui compare une seule fois chaque paire d'éléments distincts (une double boucle qui compare l'élément i à tous les éléments situés après lui, en faisant avancer i d'un cran à chaque fois) ?

Réponse : C. O(n²)

Le nombre de paires comparées vaut (n−1) + (n−2) + … + 1 = n(n−1)/2, soit 45 comparaisons pour n = 10 et 499 500 pour n = 1000. La complexité temporelle, en notation O, ne décrit que la façon dont ce nombre croît quand n devient grand : on omet donc le facteur 1/2 et les termes de degré inférieur, ce qui donne O(n²). Quand n double, le nombre de comparaisons est multiplié par 4 environ. O(n) est la complexité d'un traitement qui examine chaque élément une seule fois, et O(n log n) celle d'un traitement qui coupe les données en deux de façon répétée, comme le tri fusion.