4.31 Show that the solution of T(n)=T(n1)+n is O(n2). 4.32 Show that the solution of T(n)=T(n/2)+1 is O(lgn). 4.3-3 We saw that the solution of T(n)=2T(n/2)+n is O(nlgn). Show that the solution of this recurrence is also (nlgn). Conclude that the solution is (nlgn). 4.3-9 Solve the recurrence T(n)=3T(n)+logn by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral. 4.41 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=3T(n/2)+n. Use the substitution method to verify your answer. 4.45 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n/2)+n2. Use the substitution method to verify your