La complexité asymptotique à été inventé dans les années 1970 (vérifier****) avec le but de pouvoir comparer la performance des algorithmes indépendamment au temps d'exécution sur un ordinateur particulier.
La notation f(n) = O(g(n)) signifie qu'il existe un k tel que pour tout n suffisamment grand, k g(n) > f(n). On peut se servir de cette notation pour obtenir une approximation du comportement d'un algorithme. Par exemple, si le temps d'exécution d'un algorithme sur un ordinateur A peut être exprimé sous la forme de a n2 + b n + c et sur un ordinateur B sous la forme de d n2 + e n + f, alors on peut dire que le temps d'exécution de cet algorithme est de O(n2) indépendamment de l'ordinateur en question.
Bien évidemment, si sur un ordinateur C, le même algorithme nécessite un temps d'exécution proportionnelle à n3, la comparaison n'est plus possible. L'utilité de la complexité asymptotique dépende du modèle RAM (Random Access Machine) d'un ordinateur qui stipule que le temps d'exécution d'une opération arithmétique est borné. C'est également le cas de tout accès à des variables en mémoire.
Mais l'utilité de la complexité asymptotique repose également sur le fait que les bornes sur les opérations élémentaires se comportent de manière similaire sur tous les ordinateurs. Par exemple si sur un ordinateur particulier, l'accès à la mémoire prend 30 fois plus de temps qu'une opération arithmétique, il sera difficile de comparer un algorithme A nécessitant n accès à la mémoire et un algorithme B nécessitant n log n opérations arithmétiques, car l'algorithme A est plus rapide que l'algorithme B seulement si log n > 30 soit n > 1 000 000 000 environ, ce qui est similaire à la taille maximale de la mémoire d'un ordinateur à 32 bits.
Alors que la supposition sur les bornes similaires était assez bonne il y a une trentaine d'années, ce n'est plus le cas. Aujourd'hui (2007), un défaut de cache peut coûter des centaines de cycles d'horloge alors que l'arithmétique (même en virgule flottant) est très rapide. Il faut donc tenir compte de la localité d'un algorithme afin d'évaluer correctement sa performance.
Aujourd'hui (2007), on voit également la parution sur le marché de processeurs multi-coeurs, c'est à dire de multiple processeurs sur une seule puce. On estime que le nombre de coeurs peut suivre la loi de Moore, c'est à dire une multiplication de 2 tous les 18 mois. Dans 10 ans, il faut donc s'attendre à des processeurs de 32 coeurs. Il devient alors important d'évaluer les algorithmes par rapport à la possibilité de les paralléliser.