Given two functions f,g : R+ 7R,

1. f O(g(n)) if and only if c R+,n0 R0(n n0 (f(n) cg(n))).

2. f (g(n)) if and only if c R+,n0 R0(n n0 (f(n) cg(n))).

3. f (g(n)) if and only if O(g(n)) and (g(n)).

3. In this question, you will prove that log(n!) = (nlogn). Recall that n! = n(n1)21.

(a) Show that log(n!) O(nlogn). [Hint: log(ab) = loga + logb.]

(b) Show that log(n!) (nlogn). [Hint: Consider only the first n/2 terms.]