3. (U & G required) [40 points] Answer the following questions: (a) [20 points] Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 2T(n-1) +1. (b) [20 points] Show by substitution that the solution to T(n) = 2T +nis 0 (n?)