Problem 1 (10 points) 1. (6 points) Solve the following recurrences using any method you like and express your answer using the O() notation. Make sure your solutions are readable and understandable otherwise no points will be awarded. (2 pt) A(n) = A(n-1) + log n, A(1) = 1 (3 pts) B(n) = aB(n/3) + n, B(1)= 1. For which values of a and d is the solution equal to O(n?)? On logn)? Olog n)? (2 pts) C(n) = C(n/3) + C(n/4) + n, C(1) = 1. . . 2. (4 points) Order the following functions by order of growth. Indicate the functions that have the same growth, i.e. f(n) = (g(n)). For example if fi(n) = 2n, f2(n) = n log n and f3(n) = 2log" then fi = (/3) and fi = O(12). Make sure you briefly justify your answers. mlogn, n4/logn, n2 logn, n log(n2), loglog n, e", 102021, (n2+2n+1)}, -logn nsinn, log (n!), Vlogn log(37)