Exercise 1 (7 points). Prove that log2(n!) (n logn) . First, show that loga(n!) 3 n log2(n). So loga(n!)- O(n log2 n) (hidden con stant is 1) . Second, show that log2 (n!) > 1/4n log2(n) (for n > 4). So 1082 (n!)- (n log2 n). . If you succeed, then log2(n!) (n log2 n) follows from "First" and "Second" and Theorem 3.1, page 48. Hint: for Second" first show that log2(n!) 2 (n 1)/21 log2(In/2]) which is at least (n/2) log2(n/2) (show this for both odd and even n), then show that (n/2)log2(n/2) 2 1/4n log2(n) for n 4