Notation grand O

On rappelle la définition et les propriétés essentielles de la notation grand O.

Définitions

Soient f et g deux fonctions de N dans R+ où R+ désigne l'ensemble des nombres réels positifs. En effet puisqu'on va utiliser cette notation pour comparer les comportements asymptotiques de temps de calculs, on peut supposer sans problème que les fonctions f et g prennent des valeurs positives. On dit que f = O(g) (qui se prononce f est un grand O de g) s'il existe une constante K telle que l'inégalité suivante est vérifiée pour presque tous les entiers. Par presque tous les entiers, on entend que l'inégalitée est vraie pour tous les entiers supérieurs à un entier fixe M.

f(n) ≤ Kg(n) pour tout entier n ≥ M

Les deux éléments importants de cette définition sont les suivants. Tout d'abord, il est seulement demandé que l'inégalité soit vraie pour les entiers assez grands. Ceci signifie que l'inégalité peut tout à fait être fausse pour certains entiers mais ceux-ci doivent être en nombre fini. Ensuite, il doit exister une constante K mais il en existe bien sûr plusieurs.

Considérons les fonctions f et g définies par f(n) = 10n et g(n) = n2. Nous allons voir que la relation f = O(g) est effectivement vérifiée. Voici une table qui donne les premières valeurs des fonctions f et g.

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
g(n) 0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225
Premières valeurs des fonctions f et g.

On constante que f(n) ≤ g(n) pour tout entier n ≥ 10. En effet, on a f(n) = 10n ≤ n2 = g(n) pour n ≥ 10. On peut peut donc prendre la constante K égale à 1 et l'entier M égal à 10. Il faut remarquer que si on prend la constante K égale à 10, l'inégalité f(n) ≤ Kg(n) est vérifiée pour tout entier n ≥ 0. Dans ce cas, on peut prendre l'entier M égal à 0.

Propriétés

La propriété essentielle de la notation grand O est qu'elle constitue une relation d'ordre. Ceci signifie que si les fonctions f, g, et h vérifient f = O(g) et g = O(h), alors on a aussi f = O(h).

Par hypothèse, il existe des constantes K', K'', M' et M'' telle que f(n) ≤ K'g(n) pour tout n ≥ M' et g(n) ≤ K''g(n) pour tout n ≥ M''. Afin de pouvoir combiner les deux inégalités, on pose M = max(M', M''). Pour tout n ≥ M, on a f(n) ≤ K'g(n) ≤ K'K''h(n). On peut donc prendre K = K'K'' de façon à avoir f(n) ≤ Kh(n) pour tout entier n ≥ M.

On a ensuite les propriétés suivantes qui permettent de combiner les relations pour en obtenir facilement de nouvelles.

Exemples

Voici quelques exemples de relations entre les fonctions classiques.