Logarithme contre linéaire

Séquentielle : jusqu'à $1000$ comparaisons. Dichotomie : à chaque étape la largeur est divisée par deux, donc au plus $\lceil {\log }_{2}1000\rceil =10$ comparaisons. Le rapport est de $100$ : c'est tout l'intérêt de trier une fois pour chercher souvent (le coût du tri, $\Theta (n\log n)$, s'amortit sur de nombreuses recherches).