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