Algorithmes de complexité logarithmique, $\mathcal {O}(log n)$

Un algorithme de complexité algorithmique croit de façon linéaire en fonction de $2^n$, cela signifie que pour doubler le temps d'exécution, il faut mettre au carré le nombre de données. Par exemple, la recherche par dichotomie dans un tableau trié. Si le tableau contient $2^{30}$ éléments, il faudra à peu près $30$ itérations pour trouver l'élément recherché, contre $2^{30}$ avec une recherche séquentielle. Pour la plupart, ces algorithmes sont dans la pratique très performants.