La notation O est très utilisé en clacul de complexité, nous allons donc voir les règles de calculs qui s'appliquent à cette notation.

1) les termes constants sont exprimés par O(1)
(cas d’une instruction s’executant en un temps constant, quel que soit la taille des données)
O(c) = O(1)

2)les constantes multiplicatives sont ignorées
O(c T) = c O(T) = O(T)

3)l’addition de termes est obtenue en prenant le maximum
O(T1) + O(T2) = O(T1 + T2) = max(O(T1), O(T2))

4)la multiplication de termes reste classique
(cas d’instructions provoquant l’execution d’une autre instruction)
O(T1) × O(T2) = O(T1*T2)