Complexity Classes

  Given two nondecreasing functions of positive integers f and g,
  denote

          limit L(f,g) =    lim    f(n)/g(n)
                           n->inf

  L(f,g) is a constant that's either 0, positive, or infinite.

  We are interested in whether or not f grows faster or slower that g.
  The limit determines the *eventual* relationship as n increases.
  If the limit reaches a constant or zero, g is growing faster than f and
  is an upper bound.

  Five complexity classes:
  Given M = set of all positive monotonically increasing function of
  positive integers. A function f(x) is monotonic increasing if a < b 
  implies f(a) < f(b).

        o(g) = { f in M | L(f,g) = 0 }
        O(g) = { f in M | 0 <= L(f,g) < inf }
    Theta(g) = { f in M | 0 < L(f,g) < inf }
    Omega(g) = { f in M | 0 < L(f,g) <= inf }
    omega(g) = { f in M | L(f,g) = inf }

  We focus on O(g) ("Big Oh" or "order" of g)

  Instead of writing the more accurate f in O(g), we write f(n)=O(g(n)).
  Why, I do not know.

  Think of O(g) as set of all functions f that belong to M that "grow
  faster" (cause limit of f(n)/g(n) to become 0 or const).

  You could write the relationship as
  
  O(g(n)) = { f(n) | (c, n0) such that 0 <= f(n) <= cg(n) for all n >= n0 }
  
         
   |     cg(n)
   |     /    __ f(n)          f(n)=O(g(n)) (g(n) bounds f(n))
   |    / __--                 if f(n) <= cg(n) for some n=n0 and c
   | __/--                     witness pair: n0 and c
   |  /| 
   | / |
   |/  |
   |   |
   +---+------------> n
       n0

  So, O(g(n)) provides an ASYMPTOTIC UPPER BOUND. Not the tightest upper
  bound, though. See Theta(g) for that :-)
-------------------------------------------------------------------------------