4.3 Solving recurrences with a change of variables Sometimes, a little algebraic manipulation can make an unknown recurrence similar to one you have seen before. Let's solve the recurrence T(n)=2T(n)+(lgn) by using the change-of-variables method. a. Define m=lgn and S(m)=T(2m). Rewrite recurrence (4.25) in terms of m and S(m). b. Solve your recuurence for S(m). c. Use your solution for S(m) to conclude that T(n)=(lgnlglgn). d. Sketch the recursion tree for recurrence (4.25), and use it to explain intuitively why the solution is T(n)=(lgnlglgn). Solve the following recurrences by changing variables: Problems for Chapler 4 121 e. T(n)=2T(n)+(1). f. T(n)=3T(3n)+(n)