Définition

Soient deux fonctions $f : \mathbb{N} \mapsto \mathbb{N}$ et $g : \mathbb{N} \mapsto \mathbb{N}$, on dit que $f(N)$ est dominée par $g(N)$, aussi noté $f(N) \in O(g(N))$ s’il existe des constantes $c$ et $k$ telles que $|f(x)|<c\cdot |g(x)|$ pour tout $x>k$

$O(g(N))$ est l’ensemble des fonctions dominées¹ par $g(N)$

Propriétés

1. $O(f(N)+c)=O(f(N))$, pour toute constante $c$
2. $O(c\cdot f(N))=O(f(N))$, pour toute constante $c$
3. $O(f(N)+g(N))=O(f(N))$, si $g$ est dominée par $f$

Dominance des fonctions usuelles

Ecriture de la complexité avec $O(N)$

Les fonctions dominantes utilisées en complexité (pour un pire cas) :

• O(1) : complexité constante
• O($log_{2}(N)$) : logarithmique
• O(N) : linéaire
• O(N$\cdot log_{2}(N)$) : linéarithmique
• O($N^2$) : quadratique
• O($N^3$) : cubique
• O($N^k$) : polynomiale (avec $k$ constante)
• O($2^N$) : exponentielle

---

Issu du cours de Thomas Genet

Footnotes

1. : asymptotiquement, quand x tend vers l’infini ↩