big oh, little oh

make sure to use the notation
f \in O(x)
or
f \in o(x)
-not-
f = o(x)
...which is just -wrong-.

defn easy;
f \in o(g) iff lim_{x\to \infty} f/g = 0
f \in O(g) iff lim sup_{x\to \infty} f/g exists (is finite)
  i.e., iff there's some C s.t. f/Cg is eventually <= 1.
notably, big Oh is perhaps the first example of -lim sup-!!
(and is, frankly, good motivation for it)

More notation:
f \ll g iff f \in o(g):
a partial order

f \sim g iff f \in \Theta(g) (and hence g \in \Theta(f))
an equivalence relation

NB: there is -not- a total order on growths