1 Problem 1 (30 points total) For all the recursive formula problems below, you can assume that T(1) = T(2) = 1. Part 1: (15 points) Consider an algorithm that solves a problem of size n by dividing it into 4 pieces of size n/4, recursively solving each piece, and then combining the solutions in O(n) 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 use a proof by induction to show that the result is correct. Part 2: (7 points) Say that you have an algorithm with recurrence formula T(n) 87' (n/2) + n. Use a recursion tree to figure out the running time of your algorithm. No need for an induction proof of this one. Part 3: (8 points) Say that you have an algorithm with recurrence formula T(n) 5T (n/4) + n. Use a recursion tree to figure out the running time of your algorithm. No need for an induction proof on this one