Consider the recurrence T(n) T(n) - (1 points) 4. Draw the first six levels of the recursion tree by drawing all recursive calls of the same size on the same level. Make sure on each level you indicate the size of the recursive call and the number of recursive calls (1 points) 5. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree. 2 points) 6. Give a function g(n) and show it is an upper bound on the sum. (3 points) 7. State and prove by induction a theorem showing T(n) E O(g(n (3 points) 8. State and prove by induction (or other means) a theorem showing T(n) 2(g(n))