1 Problem 1 (30 points total) For all the recursive formula problems below, you can assume that T(2) 2. Part 1: (10 points) Say that you have an algorithm with recurrence formula T(n) = 4T(n/2) +n2. Use a recursion tree to figure out the running time of your algorithm. Then use a proof by induction to prove that vour answer is correct. Part 2: (10 points) Consider an algorithm that solves a problem of size n by dividing it into 3 pieces of size n/3, recursively solving each piece, and then combining the solutions in O(n3) time. What is the recurrence formula for this algorithm? Use a recursion tree to figure out the running time of the algorithm (in big-O notation, as always), and then check your result via a proof by induction. Part 3: (10 points) Say that you have an algorithm with recurrence formula (n)-4T(n/3) n. se a recursion tree to figure out the running time of your algorithm. Then use a proof by induction to prove that your answer is correct. (For the proof by induction, you will want to show T(n)