CHAPITRE 4 : O, Ω ET Θ : PLAFOND, PLANCHER, FOURCHETTE

Trois lettres grecques et une latine, qui font peur sans raison. Chacune répond à une question simple, et une seule.

O : « ça ne monte pas plus vite que »

Écrire f(n) = O(g(n)), c'est affirmer : à partir d'un certain point, f ne dépasse plus g, quitte à multiplier g par une constante. C'est un plafond.

La définition officielle dit la même chose en langage mathématique :

f(n) = O(g(n)) s'il existe deux constantes c > 0 et n₀ telles que f(n) ≤ c · g(n) pour tout n ≥ n₀

Deux détails rendent cette définition beaucoup moins effrayante qu'elle n'en a l'air :

« il existe » : on n'a pas besoin de trouver les meilleurs c et n₀, juste d'en exhiber un couple qui marche.
« pour tout n ≥ n₀ » : ce qui se passe avant n₀ n'est pas examiné. La notation ne parle que du comportement à long terme.

Montrer que 3n + 7 = O(n). Prenons c = 4. Il faut que 3n + 7 ≤ 4n, c'est-à-dire 7 ≤ n. Donc avec c = 4 et n₀ = 7, l'inégalité tient pour tout n ≥ 7. C'est démontré, et il n'a fallu que trouver un couple.

Le piège de O : c'est un plafond, pas une estimation

Un tri en n log n est aussi en O(n²), et en O(n⁵), et en O(2ⁿ). Toutes ces affirmations sont vraies : ce sont des plafonds corrects, simplement très généreux.

Dire « cet algorithme est en O(n⁵) » quand il est en n log n, c'est comme répondre « moins de mille ans » à quelqu'un qui demande votre âge. Exact, et parfaitement inutile.

Par convention, on annonce donc le plafond le plus serré qu'on connaisse. Mais retenez que la notation, elle, n'oblige à rien.

Ω : « ça ne monte pas moins vite que »

Oméga est l'exact symétrique : un plancher.

f(n) = Ω(g(n)) s'il existe c > 0 et n₀ tels que f(n) ≥ c · g(n) pour tout n ≥ n₀

À quoi cela sert-il ? Surtout à parler des problèmes, pas des algorithmes. On démontre par exemple que tout tri qui procède par comparaisons demande au moins n log n comparaisons. C'est une borne inférieure : elle dit qu'il est inutile de chercher mieux.

Θ : les deux à la fois

Thêta encadre : plafond et plancher, à des constantes près.

C'est la notation la plus informative : Θ(n²) dit que l'algorithme est quadratique, ni plus ni moins. Quand on peut l'écrire, il faut la préférer.

Notation	Ce qu'elle dit	Comparaison chiffrée
O(g)	f ne monte pas plus vite que g	f ≤ g
Ω(g)	f ne monte pas moins vite que g	f ≥ g
Θ(g)	f monte exactement comme g	f = g
o(g)	f monte strictement moins vite	f < g
ω(g)	f monte strictement plus vite	f > g

Les deux petites : o et ω

Le petit o exprime une domination stricte : f devient négligeable devant g.

f(n) = o(g(n)) si f(n) / g(n) tend vers 0 quand n → ∞

Ainsi n = o(n²) : rapporté à n², le terme n s'évanouit. En revanche 3n² n'est pas o(n²), car le rapport tend vers 3, pas vers 0. Il est en revanche Θ(n²).

Le petit oméga est son symétrique : f(n) / g(n) tend vers l'infini.

Ces deux-là servent surtout dans les démonstrations. Dans la pratique quotidienne, O et Θ suffisent.

Laquelle employer ?

Dans les faits, O domine l'usage, pour une raison simple : on veut surtout une garantie. « Cet algorithme ne mettra pas plus de… » est la promesse qui rassure quand on dimensionne un serveur.

Notez l'abus de langage universel : on écrit f = O(g) alors que O(g) est un ensemble de fonctions. Il faudrait écrire f ∈ O(g). Tout le monde écrit le signe égal, y compris les manuels ; sachez simplement que ce n'est pas une égalité : on ne peut pas la retourner. O(n) = f(n) ne veut rien dire.

À retenir

O est un plafond, Ω un plancher, Θ les deux ensemble.
Les deux mots qui comptent dans la définition : « il existe » et « à partir d'un certain rang ».
Un plafond correct peut être très lâche : on annonce toujours le plus serré qu'on connaît.
Θ quand on peut, O quand on veut garantir.

Exercices d'application

Exercice 1

Démontrez que 5n² + 3n + 2 = O(n²), en donnant un c et un n₀ explicites.

Voir le corrigeMasquer le corrige

Majorons chaque terme par quelque chose en n², pour n ≥ 1 :

3n  <= 3n²   des que n >= 1
2   <= 2n²   des que n >= 1

donc  5n² + 3n + 2 <= 5n² + 3n² + 2n² = 10n²

Avec c = 10 et n₀ = 1, l'inégalité f(n) ≤ c · n² tient pour tout n ≥ n₀. C'est démontré.

D'autres couples marchent aussi : avec c = 6, l'inégalité devient 3n + 2 ≤ n², vraie dès n = 4. On aurait donc pu prendre c = 6 et n₀ = 4. La définition n'exige pas le meilleur couple, juste un couple.

Exercice 2

Vrai ou faux : (a) n² = O(n³) (b) n³ = O(n²) (c) 2ⁿ⁺¹ = O(2ⁿ) (d) (n+1)! = O(n!)

Voir le corrigeMasquer le corrige

(a) Vrai. n² ne monte pas plus vite que n³ ; le plafond est juste très lâche.

(b) Faux. Aucune constante c ne peut tenir : n³ ≤ c·n² exigerait n ≤ c, ce qui finit toujours par être faux.

(d) Faux. (n+1)! = (n+1) × n!, et le facteur (n+1) n'est pas une constante : il grandit avec n. Le piège est de croire que (c) et (d) se ressemblent : dans un cas le facteur est fixe, dans l'autre il grandit.

Exercice 3

Un algorithme est en O(n²). Peut-on affirmer qu'il met quatre fois plus de temps quand les données doublent ?

Voir le corrigeMasquer le corrige

Non. O n'est qu'un plafond : il garantit que l'algorithme ne fait pas pire que quadratique. Il pourrait très bien être linéaire : un algorithme en O(n) est aussi en O(n²).

Pour affirmer que le temps quadruple, il faut Θ(n²), qui encadre par le haut et par le bas.

C'est la confusion la plus répandue du domaine, et elle se glisse jusque dans des manuels. O majore ; seul Θ décrit.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.