Big O notation provides upper bounds for the growth of functions. Intuitively for
f ∊ O(g),
f grows at most as fast as
f ∊ O(g) if and only if there is a positive number
C and a positive number ``n such that for all positive numbers
m > n we have
C⋅g(m) > f(m).
C is responsible for swallowing constant factors in the functions. If
h is two times
f, we still have
h ∊ O(g) since
C can be twice as big. For this there are two rationales:
f ∊ O(n)is preferable to
f ∊ O(7.39 n).
Cswallows constant factors, the complexity classes stay the same even on a machine ten times as fast.
n is responsible for swallowing initial turbulences. One algorithm might have an initialization overhead that is enormous for small inputs, but pays off in the long run. The choice of
n allows sufficiently big inputs to get the focus while the initial stretch is ignored.
m ranges over all values greater than
n - to formalize the idea “from
n onwards, this holds”.