• Try to establish little-oh when possible. It is easy than establishing big-oh.
• Using the ratio of n^k versus n^j for 0≤j<k, show n^j = o(n^k).
• Using the ratio of aⁿ over bⁿ, show aⁿ = o ( bⁿ ) for 1 ≤ a < b.
• You often should put things into the exponent, example: nⁿ = 2^{n lg n}.
• More complicated, e^f(n) versus e^g(n). Form ratio and get something like

         1/ef(n)( 1 - g(n)/f(n) )
  

  If g(n) = o( f(n) ) (and f is going off to infinity) then the ratio goes to zero.

1 = n1/lg n
  < lg lg* n < lg* n = lg*lg n < 2lg*n
  < ln ln n < √(lg n) < ln n < lg2 n
  <  n = 2lg n < log n! = n log n < n2 = 4lg n < n3 
  < 2√(2 log n) < √2lg n < (lg n)!  < (lg n)lg n = nlg lg n
  < (3/2)n < 2n < n 2n < en < n! < (n+1)!
  < 22n < 22n+1