Lire une borne

Majorer, sans donner une égalité

Écrire $f(x)=O(g(x))$, lorsque $g$ est positive, signifie qu’il existe une constante $C$ et un seuil $x_0$ tels que

$|f(x)|\leq Cg(x)\quad\text{pour }x\geq x_0.$

La notation $f(x)\ll g(x)$ exprime la même idée. Un indice, comme $\ll_\varepsilon$, autorise la constante à dépendre de $\varepsilon$. Les paramètres dont elle ne dépend pas sont essentiels.

Exemple

Pour $x\geq1$, on a $3x+2\leq5x$. Donc $3x+2=O(x)$. On peut aussi écrire $3x+2=O(x^2)$, mais cette dernière borne est moins précise à grande échelle.

Une équivalence est plus précise

Écrire $f(x)\sim g(x)$ signifie

$\frac{f(x)}{g(x)}\longrightarrow1.$

Ainsi, $3x+2\sim3x$, mais pas $3x+2\sim x$. Une majoration à constante près ne suffit pas à établir une équivalence.

Comparer deux résultats

Avant de comparer deux exposants, vérifie la quantité bornée, les hypothèses et les paramètres des constantes. Une borne valable pour toute une famille peut être plus forte qu’une meilleure formule valable sur quelques cas.

Enfin, « pour tout $\varepsilon>0$ » ne permet pas de remplacer directement $\varepsilon$ par zéro. La constante peut se dégrader lorsque $\varepsilon$ tend vers zéro.