PROBLEM 3: a. (3 pts) Consider the following overview of the steps taken by an algorithm: Given an array of size n, the algorithm scans the full array, then makes 5 recursive calls, each of which takes of the full array as input. Assuming n is a positive power of 5 (that is, n = 5* for some integer k> 0), write a recurrence representing the time taken to execute the algorithm on an input of size n. You do not need to consider the base case of the recurrence separately. T(n) = b. (7 pts) Consider the following recurrence, which is unrelated to the one you wrote above for part (a): T(n) = 3T(n/9) + cn for n> 1 T(1) = d Fill in the blanks of all bolded cells containing a ** in the work table below for this recurrence. The other cells are included purely to help you in your calculations and will not be graded. Depth Problem size Workode #nodes at this level Total work/level C. (6 pts) Consider the following work table for some recurrence T(n): Depth Nodes/level Workode Level (Problem size) Total work/level 0 n 2n? 2n? 1 16 2n? i n n/4 /4 1 2n/16 2n?|(421) d 16 m2 21 2n2 dn? log,n i. (4 pts) Write an expression that includes all work represented in the table, including the base-case work. You do not need to evaluate the summation component of the expression. T(n) =