Problems [Give step by step, detailed work, for full credits.] Find the order of growth of the following sums. Use the eg(n)) notation with the simplest function g(n) possible I. 2. A divide-and-conquer algorithm solves a problem by dividing its given instance into several smaller instances, solving each of them recursively, and then, if necessary, combining the solutions to the smaller instances into a solution to the given instance. Assuming that all smaller instances have the same size n/b, with a of them being actually solved, we get the following recurrence valid for n-b* ,k-0, 1,2, T(n) -aT(n/b) + f(n), where a , b 2, and f(n) is a function that accounts for the time spent on dividing the problem into smaller ones and combining their solutions (a) Show that the following formula is the solution to this recurrence for n = b ogb n f(bl) B15 The order of growth of solution T(n) depends on the values of the constants a and b and the order of growth of the function f(n) (b) What is T(n), if a = 3, b = 2, and f(n)-1, where T(1)-c which is a constant? (c) What is T(n), if a = 3, b = 2, and fin)-n, where T(1) = c, which is a constant? (d) What is T(n), if a- 3, b-2, and f(n) log n, where T(1)- c, which is a constant? 3. Using backward substitution, find the solutions for the following recurrence relations and give a bound for each of them, assume that T(1) is constant. [Give step by step work!) (a) (b) (c) T(n) = 3T(n/2) + c T(n) = 3T(n/2) + (n), T(n) = 3T(n/2) + (log: n)