Big - Oh Notation

Asymptotic Upper Bound

O  (g (n)) = { f (n) : $ constants c, n₀  '  0  £  f (n)  £  c g (n) " n   ³  n₀

from Cormen figure 2.1

If f (n) = Q ( g(n) ) then f (n) = O ( g(n) ) -- but not the other way around. F (n ) =  n² + 3 is Q ( n² ), and O ( n² )and O ( n³ ) but not Q ( n³ )

Since "Big - Oh" is an upper bound, it is often used to state the complexity of a worst case analysis. Thus insertion sort is O ( n² ). Note that the worst case bound of Q ( n² ) is not a bound on the running time for every input