2. Solving Recurrences (a) For the following recurrence relations, state which case of the Master Theorem applies and give the Big runtime bound ifn=1 T(n)- 7-T(n/2)n otherwise T(n)4T(n/2)+n + n2 otherwise if n 1 Civ) if n- T(n) = 1-Tin/2)n otherwise if n 1 +n otherwise (b) Consider the recurrence T(n) 2 T(vn +logn otherwise Solve the above recurrence using the tree method. First unroll two levels of the tree and draw this unrolling as a tree. Finish your analysis by completing the missing entries of this table. of nodes at level i input size at level i work per node at level i total work at level i level of base case number of nodes in the base case level for recursive work expression for non recursive work closed form for total work t Big-e for the total work