Big Oh Hints

1. Show log log n = O(log n).
   First we show log n = O(n). We suppose that the reader knows that log is a concave function, that the tanget of log n at 1 is always about log n and has slope (d log n)/(d n) evaluated at 1. Call this slope k. Then log n <= kn. (Draw a picture) for n>=1.
   Log n is monotonic, that is, if n<m then log n < log m. Since for large enough n, log n <= kn, then for such n, log log n < log n + log k. Log k is a constant, so log k = O(log n), therefore log n + log k = O(log n) (Proposition 3.16, 2 and 1).
   So for a perhaps even larger n, there is a c such that log log n < log n + log k < c log n. Conclusion, log log n = O(log n).
2. Show log n = O(log^2 n)
   let n_o be such that log n > 1 for n > n_o. Then log n < log^2 n.
3. Show log log n = O(log^2 n)
   log log n = O(log n) and log n = O(log^2 n). So log log n = O(log^2 n) (Proposition 3.16, 4).
4. Show n = O(n log n)
   Let n_o be such that log n > 1, then n < n log n.
   Another way: n = O(n), 1 = O(log n), so n = O(n log n) (Proposition 3.16, 3).
5. n^2 log n = O(n^3)
   n^2 = O(n^2) and log n = O(n). Apply 3.16, 3 again.
6. Compare 6 n log n to n log_4 n.
   6 n log n = O(n log n) (Either use n_o so that n log n is positive and k = 6 or Proposition 3.16, 1).
   Also n log_4 n = n (log_4 2) (log n) = O(n log n). So 6 n log n = Theta( n log_4 n).