Problem 4: (15 points, 3 points each part) For each of the following problems, indicate the complexity class (g(n)) the function belongs to. Justify your conclusion with a brief proof. You don't need to go crazy with the formality of your proofs, but you must show your reasoning clearly. Remember that for you must prove an upper and a lower bound. a) (n? + 1)10 b) V10n2 + 7n + 3 c) 2n ln(n + 2)2 + (n + 2)2 in (*) d) 21+1 + 3n-1 e) [log2 n] Hints: You may find the addition theorem useful: If f(n) e (a(n) and g(n) e (b(n)) then f(n) + g(n) e (max ( a(n), b(n)) For part e: recall that for any x, x 1 5 [x] SX 1