Complexité dans le pire des cas

Pour la recherche d'un élément dans une liste, la recherche séquentielle qui consiste à considérer tous les éléments les uns après les autres jusqu'à avoir trouvé la cible (si elle existe), a une complexité dans le pire cas qui est de l'ordre de la taille de la liste : l'élément peut être à la toute fin. Par contre la complexité dans le meilleur des cas est constante : l'élément peut se trouver en début de liste. Et la complexité moyenne (pour une distribution uniforme) est aussi de l'ordre de la taille de la liste.

Le tri rapide avec choix du pivot arbitraire sur une liste de taille ${\displaystyle n}$ a une complexité en ${\displaystyle O(n\log(n))}$sur des permutations aléatoires. Toutefois, si l'entrée est déjà triée, le principe diviser pour régner perd son intérêt et la complexité est alors en ${\displaystyle O(n^{2})}$.