Le pire cas n'est pas la moyenne

Si l'élément est en position $i\in \{0,\dots ,n-1\}$, l'algorithme réalise $i+1$ itérations. Par hypothèse d'uniformité, chaque position a une probabilité de $1/n$ d'apparaître : $$\text{Couˆt moyen}=\frac{1}{n}\sum _{i=0}^{n-1}(i+1)=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}\approx \frac{n}{2}$$ Le coût moyen est de $n/2$ opérations, ce qui reste linéaire $O(n)$, tout comme le coût dans le cas le pire qui vaut $n$ opérations. On privilégie le cas le pire car :

1. Il offre une garantie stricte de temps de réponse, sans dépendre d'hypothèses sur la distribution des données réelles (qui ne sont pas toujours uniformes).
2. Dans de nombreuses applications, l'élément cherché est absent, ce qui force l'algorithme à exécuter systématiquement le cas le pire.
3. Le calcul théorique du cas le pire est plus simple car il n'exige pas d'introduire de modèle de probabilité sur les entrées.