Chaque graphique est en échelle log-log : horizontalement n, verticalement le temps d'une opération. Sur cette échelle, une loi de puissance devient une droite, et la pente se lit directement : plate = O(1), pente 1 = O(n), pente 2 = O(n²). Le tableau du bas donne la théorie et la croissance réellement mesurée.

Comparaison asymptotique des fonctions utilisées

n : nombre d'objets. k : nombre de résultats demandés. c : nombre de cellules touchées par une requête. C : nombre de couples candidats testés. p : nombre de cœurs. inv : nombre d'inversions de l'ordre trié entre deux images. Les cases marquées * dépendent surtout de la répartition des objets, pas seulement de n : c'est le cas de toutes les structures à découpage adaptatif, et c'est précisément ce que les mesures font apparaître.

Théorie contre mesures

Facteur de croissance entre la plus petite et la plus grande taille de la campagne, comparé au facteur attendu par la théorie. Un badge vert signale un écart inférieur à 2,5, orange jusqu'à 5, rouge au-delà. Les écarts rouges ne sont pas des erreurs : une structure dont le coût est dominé par une constante, ou qui franchit un seuil, s'écarte de sa loi asymptotique aux tailles mesurées.