complexité dans le pire des cas

En informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles. Elle est exprimée comme une fonction de la taille de l'entrée de l'algorithme. Implicitement, on cherche à construire des algorithmes s'exécutant en utilisant le moins de ressources possible (e.g. le plus vite possible), et il s'agit par conséquent d'une borne supérieure des ressources requises par l'algorithme. Par exemple, la complexité en temps dans le pire des cas correspond au temps d'exécution le plus long que puisse avoir l'algorithme, et permet d'en garantir la terminaison. La complexité dans le pire des cas permet de comparer l'efficacité de deux algorithmes. Elle s'oppose à la complexité en moyenne.