I need help with this question

Homework 06: Analysis, sorting, and graphs Due date: May 25, 2018 at 11:59 pm Instructions: Submit a typed or neatly handwritten scan of your responses on Canvas in PDF format. Note: you will need to submit a separate PDF per each section. 1. The tree method and the master method Submit your answers here: https://canvas.uw.edu/courses/1199402/assignments/4254932 Consider the following recurrence A(t) 5A/ otherwise We want to find an exact closed form of this equation by using the tree method. (a) Suppose we draw out the total work done by this method as a tree, as discussed in lecture. Including the base case, how many levels in total are there? Your answer should be a mathematical expression which uses the variable p, which represents the original number we passed into Alt) (b) How many nodes are there on any given level i? Your answer should be a mathematical expression that uses the variable i Note: let i 0 indicate the level corresponding to the root node. So, when equal to 1 0, your expression should be (c) How much work is done on the i-th recursive level? Your answer should be a mathematical expression that uses the variables i and p ?. (d) How much work is done on the final, non-recursive level? Your answer should be a mathematical expression that uses the variable p. (e) What is the closed form of this recurrence? Be sure to show your work. Note: you do not need to simplify your answer, once you found the closed form. Hint: You should use the finite geometric series identity somewhere while finding a closed form. (f) Use the master theorem to find a big-e bound of A(t)