Nous avons déjà rencontré la notation 'O' que nous rappelons ici, et à laquelle nous allons adjoindre d'autres notations également d'un usage courant pour exprimer des 'relations asymptotiques' entre les suites.
Historiquement ces notations ont été introduites pour comparer des suites particulières correspondant à l'efficacité de certains algorithmes en fonction de la taille des objets traités. Par exemple en fonction de n le nombre d'opérations (donc le temps) nécessaire(s) pour trier un tableau de taille n. Le but était alors de comparer les performances des divers algorithmes (tris à bulles, tris par sélection, tri par insertion, tri 'Shell', tri 'rapide',etc...). Ces notations ont été largement employées par le mathématicien Edmund Landau, mais leur 'paternité' de l'avis des historiens des sciences, reviendrait à son aîné Paul Bachmann.

Galeries des portraits

Edmund Landau (Allemagne-1877:1938) Paul Bachmann (Allemagne-1837:1920)

La notation O

La relation 'O' est une relation de 'domination' d'une suite par une autre. La lettre O est utilisée parce que le rythme de croissance d'une suite est aussi appelée son 'ordre'.
On écrit v=O(u) ou v(n)=O(u(n)) s'il existe une constante positive K telle que pour n suffisamment grand |v(n)|≤Ku(n). Soit encore: ∃ N | n≥N ⇒ |v(n)|≤K|u(n)|.
Remarquons tout de suite qu'en cas d'existence la constante K n'est pas unique puisque si K 'fonctionne' K+1 aussi. Par ailleurs si K1 est tel que |v(n)|≤K1|u(n)| pour n≥N1, rien n'empêche de trouver K2<K1 et N2>N1 tels que |v(n)|≤K2|u(n)| pour n≥N2.

Remarque

La notation ci-dessus est courante, mais elle n'est pas très rigoureuse. En particulier elle viole la sémantique du symbole '='. Pour être parfaitement rigoureux il faudrait que O(u) désigne une classe de suites et écrire en toute rigueur v ∈ O(u). Cependant l'écriture v=O(u) est courante et nous l'adopterons sachant qu'il s'agit d'un abus d'écriture.

Exemples:

Arithmétique de O

Les résultats suivants sont pratiquement évidents:
Si v et w sont O(u) alors u+w est aussi O(u).
Si v est O(u) et si λ est une constante, λv est également O(u).
Les abus d'écriture relevés plus haut permettent donc d'autres écritures étranges comme:

Ordres de grandeur des suites croissantes (aussi appelée 'complexité'):

c désigne une constante:

La notation Θ

v=Θ(u) signifie, par définition que v=O(u) et u=O(v).
Donc ∃ K et ∃H tels que pour n suffisamment grand |v(n)|≤K|u(n)| et |u(n)|≤H|v(n)|.
Signalons tout de suite que souvent la notation O est utilisée en lieu et place de Θ surtout dans les manuels d'algorithmique. C'est regrettable, mais c'est ainsi. Le plus souvent c'est sans importance parce qu'on a seulement besoin d'une relation de majoration.
Une condition suffisante pour que v=θ(u) est que limn→∞u(n)/v(n) existe et soit non nulle.
La démonstration est immédiate. Encore une fois, cette condition suffisante n'est nullement nécessaire.

La notation o

On écrit v=o(u) ou bien v(n)=o(un) Si limn→∞v(n)/u(n)=0
On dit encore dans ce cas que v est 'négligeable devant u'.
La même remarque sur les abus d'écriture (voir notation 'O') s'applique à la notation 'o'.

Exemples

Arithmétique de o

On a les relations suivantes: Pour d'autres relations voir par exemple cet exercice.