Définition 4.1.(Notation de Landau)On dit que f=O(g) s'il existe deux nombres rééls k,a > 0 tels quepour tout x>a, |f(x)|≤k|g(x)|.
Exemple 4.1.Les figures permettent de comparer les fonctions usuelles utilisées pour décrire la complexité d'un algorithme en fonction de la taille n des données d'entrées. Parmi les fonctions usuelles, le log à base 2 de n (log2(n)) joue un rôle important.
Si le nombre d'instructions est égal à f(n)=a n2 + b n + c avec a,b,c des constantes réelles, alors f(n)=O(n2).
Définition 4.2. On définit les trois complexités suivantes :Soit Dn l'ensemble des instances de taille n. Si toutes les instances sont équiprobables, on a
- Complexité dans le pire des cas
C>A(n)=max{CA(d),d donnée de taille n} - Complexité dans le meilleur des cas
C<A(n)=min{CA(d),d donnée de taille n} - Complexité en moyenne
où Pr(d) est la probabilité d'avoir en entrée une instance d parmi toutes les données de taille n.

fonction suite(val n:entier):entier;
var i,s:entier;
début
s=0;
pour i allant de 1 à n faire
s=s+i;
finpour;
retourner(s)
fin
finfonction;
Source Python
fonction jeuDePile(val n:integer):booléen;
var i: entier;
début
pour i allant de 1 à n faire
f=résultat_lancer_pièce()
si (f==pile) alors
retourner(VRAI)
finsi
finpour
retourner(faux)
fin
finFonction
Source Python