Comparaison asymptotique

Soit f et g les fonctions réelles définies par les formules${\displaystyle f(x)=\cos(x)+2{\text{ et }}g(x)=x.}$

Par une étude des deux fonctions, on sait que g prend des valeurs aussi grandes que l'on veut au voisinage de l'infini, tandis que f ne peut prendre des valeurs qu'entre 1 et 3. Le quotient g divisé par f au voisinage de l'infini ne cesse d'augmenter et n'est pas borné. Dans ce contexte, on peut dire que f est négligeable devant g, ou que g est prépondérante devant f, au voisinage de l'infini, on écrit (notation de Landau[2]) :

${\displaystyle f(x)=o(g(x))\ (x\rightarrow \infty )}$

ou (notation de Hardy[1] - [3], désuète[4])

${\displaystyle f(x)\prec g(x)\ (x\rightarrow \infty ).}$

La notation de Hardy permet d'enchaîner les relations de prépondérance, par exemple :

${\displaystyle \cos(x)\prec \ln(x)\prec x\prec x^{2}\prec \exp(x)\prec x^{x}\ (x\rightarrow \infty ).}$

Pour définir formellement cette propriété on considère le comportement du quotient ${\displaystyle {\frac {f}{g}}}$.

Soit ${\displaystyle a\in \mathbb {R} \cup \left\{+\infty$ ;-\infty \right\}.}

Soient f et g deux fonctions de la variable réelle x. On suppose que g ne s'annule pas sur un voisinage de a[5]. On dit que f est négligeable devant g, ou que g est prépondérante[6] devant f en a, et on note ${\displaystyle f(x)={\underset {\overset {x\rightarrow a}{}}{o}}(g(x))}$, lorsque

${\displaystyle {\frac {f(x)}{g(x)}}{\underset {\overset {x\rightarrow a}{}}{\longrightarrow }}0.}$

Si le contexte est clair, on ne précise pas le domaine d'étude et on note : ${\displaystyle f(x)=o(g(x))}$, voire ${\displaystyle f=o(g)}$. Cependant, la notation est toujours associée à un lieu a et au voisinage de ce lieu : être négligeable est un concept local.

Dans cette notation de Landau ${\displaystyle f(x)=o(g(x))}$ (parfois aussi ${\displaystyle f(x)\in o(g(x))}$), le symbole ${\displaystyle o}$ se lit petit o. La notation équivalente de Hardy est ${\displaystyle f(x)\prec g(x)}$. On utilise aujourd'hui exclusivement la notation de Landau.

Par abus de langage[7], on effectue des « opérations » sur les « petits o », c'est-à-dire sur les négligeables. En effet, on peut dire que :

• ${\displaystyle o(f)+o(f)=o(f)}$ ;
• ${\displaystyle o(f)-o(f)=o(f)}$.

• ${\displaystyle x^{2}+10000={\underset {\overset {x\rightarrow \infty }{}}{o}}(x^{3})}$
• ${\displaystyle x^{n}={\underset {\overset {x\rightarrow +\infty }{}}{o}}(e^{x})}$
• Pour toute fonction ${\displaystyle \varepsilon }$, telle que ${\displaystyle \varepsilon (x){\underset {\overset {x\rightarrow a}{}}{\longrightarrow }}0}$, on a : ${\displaystyle \varepsilon (x)={\underset {\overset {x\rightarrow a}{}}{o}}(1)}$

Soit ${\displaystyle a\in \mathbb {R} \cup \left\{+\infty$ ;-\infty \right\}} .

Soient f et g deux fonctions de la variable réelle x. On suppose que g ne s'annule pas sur un voisinage de a. On dit que f est équivalente à g en a, ou que g équivaut à f en a, et on note

${\displaystyle f(x){\underset {\overset {x\rightarrow a}{}}{\sim }}g(x)}$, lorsque ${\displaystyle f(x)-g(x)={\underset {\overset {x\rightarrow a}{}}{o}}(g(x))}$.

${\displaystyle \cos x+x^{20}+\exp(x){\underset {\overset {x\rightarrow \infty }{}}{\sim }}\exp(x)}$

La notation grand O de Landau dénote le caractère dominé d'une fonction par rapport à une autre.

Généralement, comme Paul Bachmann qui a introduit ce symbole en 1894, on utilise la lettre O majuscule (de l'allemand Ordnung, « ordre »). C'est beaucoup plus tard (1976), par analogie avec le symbole oméga majuscule Ω (voir plus bas), que Donald Knuth a discrètement suggéré de rebaptiser le symbole O du nom de la lettre omicron majuscule[8] (qui n'apparaît que dans le titre de son article), celle-ci étant rarement dessinée de manière clairement différente du O. Dans les deux cas, le symbole utilisé est distinct du symbole 0 (zéro)

Soient f et g deux fonctions de la variable réelle x. On dit que f est dominée par g en +∞, ou que g domine f en +∞, et on note (notation de Bachmann, 1894, ou de Landau, 1909)

${\displaystyle f(x)=O(g(x))\ (x\rightarrow \infty ),}$

ou (notation de Hardy[1], 1910, désuète)

${\displaystyle \ f\preccurlyeq g,}$

ou encore (notation de Vinogradov, années 1930)

${\displaystyle f(x)\ll g(x)\ (x\rightarrow \infty ),}$

lorsqu'il existe des constantes N et C telles que

${\displaystyle \forall x>N\qquad \left|f(x)\right|\leq C\left|g(x)\right|.}$

Intuitivement, cela signifie que f ne croît pas plus vite que g.

De même, si a est un nombre réel, nous écrivons

${\displaystyle f(x)={\underset {x\to a}{O}}(g(x))}$

s’il existe des constantes d > 0 et C telles que

${\displaystyle \forall x\qquad \left|x-a\right|<d\Rightarrow \left|f(x)\right|\leq C\left|g(x)\right|.}$

Ceci est équivalent, lorsque g ne s'annule pas, à ${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .}$

• ${\displaystyle 4x^{3}+10000x^{2}={\underset {x\to \infty }{O}}(x^{3}).}$
• ${\displaystyle x^{3}={\underset {x\to \infty }{O}}(4x^{3}+10000x^{2}).}$
• En un point a, si f est négligeable devant g ou équivalente à g, alors elle est dominée par g.
• Une fonction f est bornée sur un voisinage de a si et seulement si ${\displaystyle f(x)={\underset {x\to a}{O}}(1)}$.

En 1914, Hardy et Littlewood ont introduit le nouveau symbole Ω[9] défini ainsi :

${\displaystyle f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0}$.

Les fonctions f et g sont supposées définies, et g positive, dans un voisinage de l'infini. Ainsi ${\displaystyle f(x)=\Omega (g(x))}$ est la négation de ${\displaystyle f(x)=o(g(x))}$.

En 1916, les mêmes auteurs introduisent les deux nouveaux symboles Ω_R et Ω_L[10], définis de la façon suivante :

${\displaystyle f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0}$;

${\displaystyle f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0}$.

Comme avant, les fonctions f et g sont supposées définies, et g positive, dans un voisinage de l'infini. Ainsi, ${\displaystyle f(x)=\Omega _{R}(g(x))}$ est la négation de ${\displaystyle f(x)<o(g(x))}$, et ${\displaystyle f(x)=\Omega _{L}(g(x))}$ la négation de ${\displaystyle f(x)>o(g(x))}$.

Contrairement à ce qu'affirmera plus tard D.E. Knuth[8], Edmund Landau a également utilisé ces trois symboles en 1924[11].

Ces notations de Hardy et Littlewood sont des prototypes, qui après Landau semblent n'avoir jamais été utilisés tels quels : Ω_R est devenu Ω₊, et Ω_L est devenu Ω_–.

Ces trois symboles sont maintenant couramment utilisés en théorie analytique des nombres, de même que ${\displaystyle f(x)=\Omega _{\pm }(g(x))}$ pour signifier que les conditions ${\displaystyle f(x)=\Omega _{+}(g(x))}$ et ${\displaystyle f(x)=\Omega _{-}(g(x))}$ sont toutes deux satisfaites.

Il est clair que dans chacune de ces définitions on peut remplacer ∞ par –∞ ou par un nombre réel.

On a

${\displaystyle \sin x=\Omega (1)\ (x\rightarrow \infty )}$

et plus précisément,

${\displaystyle \sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).}$

On a

${\displaystyle \sin x+1=\Omega (1)\ (x\rightarrow \infty )}$

et plus précisément,

${\displaystyle \sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty )~;}$

cependant,

${\displaystyle \sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).}$

Il est important de souligner le fait que l'écriture

${\displaystyle f(x)=\Omega (g(x))\ (x\rightarrow \infty )}$

possède en mathématiques deux définitions incompatibles, toutes les deux très répandues, l'une en théorie analytique des nombres, qu'on vient de présenter, l'autre en théorie de la complexité des algorithmes. Lorsque ces deux disciplines se rencontrent, cette situation est susceptible de créer une grande confusion.

En 1976, Knuth publie un article[8] dont le but principal est de justifier son utilisation du même symbole Ω pour décrire une autre propriété que celle décrite par Hardy et Littlewood. Il tente de convaincre le lecteur que la définition de Hardy et Littlewood n'est quasiment jamais utilisée (ce qui, même en 1976, est faux depuis en tout cas 25 ans[12]). Il va jusqu'à prétendre que Landau ne l'a jamais utilisée (ce qui est également faux[11]). Il ressent impérativement le besoin d'une autre notion (« For all the applications I have seen so far in computer science, a stronger requirement […] is much more appropriate »), et a décidé que l'utilisation du symbole Ω doit être réservé pour la décrire. Il est fortement contrarié par l'ancienne définition (« Unfortunately, Hardy and Littlewood didn't define Ω(f(n)) as I wanted to »).

Il prend donc le risque de créer la confusion, et définit

${\displaystyle f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))}$[13].

En mathématiques, il est souvent important de garder un œil sur le terme d'erreur d'une approximation. Cette notation est particulièrement utilisée dès que l'on a affaire à des développements limités et à des calculs d'équivalents. Par exemple, le développement de la fonction exponentielle à l'ordre 2 peut aussi s'écrire :

${\displaystyle e^{x}=1+x+{\frac {1}{2}}x^{2}+o(x^{2})\ {\rm {quand}}\ x\rightarrow 0}$

pour exprimer le fait que l'erreur, la différence ${\displaystyle e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right)}$, est négligeable devant ${\displaystyle x^{2}}$ quand ${\displaystyle x}$ tend vers 0.

Il faut préciser que le nombre d'opérandes dans ce genre d'écriture doit être borné par une constante qui ne dépend pas de la variable : par exemple l'assertion ${\displaystyle o(x)+o(x)+\dots +o(x)=o(x)}$ est évidemment fausse si les points de suspension cachent un nombre de termes qui n'est pas borné lorsque x varie.

Voici une liste de catégories de fonctions couramment utilisées en analyse. La variable (notée ici n) tend vers +∞ et c est une constante réelle arbitraire. Lorsque c est une constante supérieure à 1, les fonctions apparaissent dans cette liste par ordre croissant de grandeur.

O(n^c) et O(cⁿ) sont très différents. Le dernier autorise une croissance bien plus rapide, et ce pour n'importe quelle constante c > 1. Une fonction qui croît plus rapidement que n'importe quel polynôme est dite superpolynomiale. Une fonction qui croît plus lentement que toute exponentielle est dite sous-exponentielle. Il existe des fonctions à la fois superpolynomiales et sous-exponentielles, comme la fonction n^log(n).

Remarquons aussi que O(log n) est exactement identique à O(log(n^c)), puisque ces deux logarithmes sont multiples l'un de l'autre par un facteur constant et que la notation grand O « ignore » les constantes multiplicatives. De manière analogue, les logarithmes dans des bases constantes différentes sont équivalents.

La liste précédente est utile à cause de la propriété suivante : si une fonction f est une somme de fonctions, et si une des fonctions de la somme croît plus vite que les autres, alors elle détermine l'ordre de croissance de f(n).

Exemple :

si f(n) = 10 log(n) + 5 (log(n))³ + 7 n + 3 n² + 6 n³,
alors f(n) = O(n³).

Cette notation peut aussi être utilisée avec des fonctions de plusieurs variables :

L'écriture :	${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\;}$ quand ${\displaystyle m,n\to +\infty }$
correspond à la proposition :	${\displaystyle \exists C\quad \exists N\quad \forall n,m>N\qquad |f(n,m)-n^{2}-m^{3}|\leq C(n+m)}$

Pour certains, cette notation abuse du symbole d'égalité, puisqu'elle semble violer l'axiome d'égalité : « des choses égales à la même chose sont égales entre elles » (autrement dit, avec cette notation, l'égalité n'est plus une relation d'équivalence). Mais on peut également considérer que dans l'écriture

${\displaystyle f(n,m)-n^{2}-m^{3}=O(n+m),}$

la notation "=O" désigne un seul opérateur, dans l'écriture duquel le signe "=" n'a pas d'existence propre indépendante (et en particulier ne désigne pas une relation d'équivalence). Il n'y a dans ce cas plus d'abus de notation, mais évidemment toujours un risque de confusion. Il est également possible de définir O(g(x)) comme un ensemble de fonctions, dont les éléments sont toutes les fonctions qui ne grandissent pas plus vite que g, et d'utiliser les notations ensemblistes pour indiquer si une fonction donnée est un élément de l'ensemble ainsi défini. Par exemple :

${\displaystyle f(n,m)-n^{2}-m^{3}\in O(n+m),}$

Les deux conventions sont couramment utilisées mais la première (et plus ancienne) est jusqu'au début du XXI^e siècle la plus souvent rencontrée. Pour éviter ce problème on utilise (tout aussi couramment) la notation de Vinogradov (voir ci-dessous).

${\displaystyle f(n,m)-n^{2}-m^{3}\ll n+m,}$

Un autre problème est qu'il faut clairement indiquer la variable par rapport à laquelle le comportement asymptotique est examiné. Une affirmation telle que ${\displaystyle f(n,m)=O(m^{n})\;}$ n'a pas le même sens selon qu'elle est suivie de « quand ${\displaystyle m,n\to +\infty }$ » ou, par exemple, de « (pour tout ${\displaystyle m}$ fixé) quand ${\displaystyle n\to +\infty }$ ».

Les notations de Landau portent le nom du mathématicien allemand spécialisé en théorie des nombres Edmund Landau qui utilisa le symbole O[2], introduit primitivement par Paul Bachmann[14], et s'en inspira pour inventer le symbole o. Il n'utilisa le symbole Ω que dans un seul article en 1924[11], pour signifier ≠ o ; cette notation avait été introduite (avec la même signification) en 1914 par G. H. Hardy et J. E. Littlewood[9] ; depuis, Ω est couramment utilisé en théorie des nombres, mais exclusivement dans ce même sens, et jamais dans le premier sens indiqué dans le tableau ci-dessus. Dans le même article Landau utilise les symboles Ω_R et Ω_L, également dus à Hardy et Littlewood[10], (et depuis notés Ω₊ et Ω_–) pour signifier ${\displaystyle \not <o}$, respectivement ${\displaystyle \not >o}$. Il utilise bien sûr également la notation ∼, mais jamais ω ou Θ.

Les notations de Hardy ${\displaystyle \preccurlyeq }$ et ${\displaystyle \prec }$, introduites par G. H. Hardy dans son tract de 1910 Orders of Infinity[1], jouent le même rôle que celles de Landau pour la comparaison asymptotique des fonctions.

En notation de Landau, on peut les définir comme suit :

${\displaystyle f\preccurlyeq g\iff f=O(g)}$

et

${\displaystyle f\prec g\iff f=o(g).}$

Les notations de Hardy sont désuètes. Hardy a rapidement abandonné ses propres notations ; il utilise les notations de Landau dans tous ses articles (soit près de 400 !) et dans ses livres[15] sauf dans son tract de 1910 et dans 3 articles (1910-1913). On peut noter que si Hardy a introduit dans son tract de 1910 quelques autres symboles pour la comparaison asymptotique des fonctions, il n'a par contre jamais défini ou utilisé la notation ${\displaystyle \ll }$ (ou ${\displaystyle \prec \!\!\prec }$), qu'on doit à Vinogradov.

Le théoricien des nombres russe Ivan Matveyevich Vinogradov introduisit dans les années 1930[16] la notation qui porte son nom,

${\displaystyle f\ll g\iff f=O(g)}$.

La notation ≪ de Vinogradov est couramment utilisée en théorie des nombres à la place de O ; parfois même les deux notations sont utilisées indifféremment dans le même article.

En 1982, Carl Pomerance a introduit une nouvelle notation pour abréger les fonctions complexes intervenant dans l'étude asymptotique de la complexité des algorithmes. Ainsi, par exemple, une fonction f appartient à la classe ${\displaystyle L_{n}[\alpha ,c]}$ si on a ${\displaystyle f=\exp \left((c+o(1))\log(n)^{\alpha }(\log \log n)^{1-\alpha }\right)}$ ; l'exponentielle « écarte » suffisamment les fonctions pour qu'il ne soit pas possible de ramener cette notation à la forme ${\displaystyle f=O(g)}$ par exemple.

Les notations de Landau en particulier conduisent à des abus de notation très fréquents, tels que d'écrire ${\displaystyle f=o(g)\Rightarrow 2f=o(g)}$ ou pire encore ${\displaystyle o(g)-o(g)=o(g)}$ ; cette deuxième notation doit se lire en utilisant un langage ensembliste : en appelant ${\displaystyle A}$ l'ensemble des fonctions négligeables par rapport à ${\displaystyle g}$ et ${\displaystyle B=A-A}$ l'ensemble des différences de deux fonctions de ${\displaystyle A}$, elle signifie que ${\displaystyle B\subset A}$. Plus généralement ces abus de notation reviennent à considérer la notation ${\displaystyle o(g)}$ (ou ${\displaystyle O(g)}$, etc.) comme représentant une classe de fonctions, et ${\displaystyle f=O(g)}$ comme signifiant que ${\displaystyle f}$ appartient à cette classe.

• Développement asymptotique
• Fonction asymptotique
• Vitesse de convergence des suites
• Échelle de comparaison
• Combinatoire analytique

(en) Big-O Cheat Sheet, un site répertoriant une classification des complexités algorithmiques par domaine.