Q1 (15 points) For each of the following pairs of functions f(n) and g(n), decide whether we have f(n) 0(g(n)), f(n) 82(g(n)), or f(n) (g(n)). On the answer sheet, check every box that is true. (a) f(n) = 100n + 10000, g(n) = nlgn - 10000. (b) f(n) = nIgn, g(n) = 2-1 . (c) f(n) = 1=1, g(n) = nlgn. (d) f(n) = n, g(n) = 1.01". (e) f(n) = 2", g(n) = n! Q2 (15 points) There are two algorithms A and B for solving the same problem. Algorithm A has a worst-case time complexity TA(n) that satisfies the recurrence relation TA(n) = 8.TA(n/2) + 10n?, where n is the input size. Algorithm B has a worst-case time complexity TB(n) that satisfies the recurrence relation Te(n) = 7. TB(n/2) + 200n? Ign, where n is the input size. (a) Use the Master method to solve for TA(n). On the answer sheet, decide which case of the Master method TA(n) falls into, by checking the corresponding box. (b) On the answer sheet, decide the asymptotic notation of TA(n) by checking the corre- sponding box. (c) Use the Master method to solve for TB(n). On the answer sheet, decide which case of the Master method TB(n) falls into, by checking the corresponding box. (d) On the answer sheet, decide the asymptotic notation of TB(n) by checking the corre- sponding box