1. Algorithm X is a recursive algorithm that takes in an array of size n and makes two recursive calls of size n ? 1, one call of size n ? 2, and it takes ?(1) for all of its non-recursive code. It has base cases of n = 1 and n = 0. Give a recurrence and draw a recurrence tree for Algorithm X. Note that you do not need to evaluate the complexity of this recurrence.

2. Professor Muffett is trying to develop Algorithm Y . She has come up with a ?(n2) algorithm to combine subproblems of size n/4 to solve the original problem of size n. What is the largest number of recursive calls can she make so that Algorithm Y is faster than the state-of-the-art ?(n^3) algorithm? Justify your answer.

3. Professor Muffett is also working on Algorithm Z to solve a different prob- lems. On this problem, her grad student came up with an algorithm that can solve the problem by breaking it up into 5 equal-sized pieces, recur- sively solving those problems, and combining the solutions together in ?(n) time. What is the largest size that these recursive calls can be if she needs to beat a ?(n^2 lg n) algorithm?