Big - Oh Notation

Asymptotic Upper Bound

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

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 ) =  n2 + 3 is Q ( n2 ), and O ( n2 )and O ( n3 ) but not Q ( n3 )

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 ( n2 ). Note that the worst case bound of Q ( n2 ) is not a bound on the running time for every input

Growth of Functions - 3 of 5