Une même suite de 1000 valeurs est représentée par un tableau, puis par une liste chaînée. Deux opérations sont comparées : atteindre le 500e élément, et insérer une valeur.
Objectif
Chiffrer les deux opérations dans les deux représentations.
Ce que le comptage ne dit pas
Les cases d'un tableau se suivent en mémoire, donc la machine les lit par blocs et anticipe la suite. Les nœuds d'une liste sont dispersés, et chaque saut coûte. À nombre d'opérations identique, un parcours complet de tableau bat un parcours de liste de plusieurs fois, et cet écart n'apparaît dans aucun comptage d'étapes.