La complexité temporelle décrit comment le temps d'exécution d'un algorithme évolue en fonction de la taille de l'entrée. On compte le nombre d'opérations élémentaires plutôt que des secondes, ce qui rend la mesure indépendante de la machine. Elle sert à comparer des algorithmes et à prévoir leur comportement sur de grandes données.
Exemple
Chercher une valeur dans une liste non triée de n éléments demande jusqu'à n comparaisons.