Une recherche linéaire compare un à un, depuis le début, les éléments d'un tableau de 100 valeurs distinctes pour trouver une valeur cible. Si la cible se trouve toujours dans le tableau et a la même probabilité d'être à n'importe quelle position, quel est le nombre moyen de comparaisons ?

Réponse : B. 50,5

Si la cible est à la position k, la recherche effectue k comparaisons ; la moyenne vaut donc (1 + 2 + … + 100) / 100 = 50,5, soit (n + 1)/2 en général. Le meilleur cas (cible en tête) demande 1 comparaison et le pire cas (cible à la fin) 100 ; la moyenne comme le pire cas sont proportionnels à n, d'où une complexité temporelle en O(n). Environ 7 correspond à log₂ 100 ≈ 6,6, le nombre d'étapes d'une recherche dichotomique, qui n'est utilisable que si les données sont triées.