The numbering to follow:

Part 3 - Master Method Show that the solution to the following recurrence is O(n2), using the Master Method: (n)=4(2n)+n Make sure to provide the same level of detail, with the same numbering, as in Part 1 Part 4- Recursion Tree For the recurrence of Part 3 , using the recursion tree method, show that you get the same result, i.e. O(n2). Make sure to exhaustively comment on these three steps: 1. Draw out the recursion tree for at least three levels (i.e. there are recursive terms only at the third level) 2. Come up with a generalized summation formula that sums up each level, over all levels. For this you need to figure out, what the generalized form of the sum is at each level, then you need to find how many levels you have altogether. 3. Interpret the formula of step 2 to show that the net result is bounded by O(n2) 1. Determine the relevant parameters, i.e. a,b and f(n) 2. Provide the value for nlogb(a) 3. Provide a hypothesis for the case that likely applies 4. Determine the correct epsilon, if applicable (i.e. if you have a case 1 or 3 ) 5. Apply the master theorem and provide the solution