(1) (8 POINTS) Consider the recurrence T(n) = 4T(n/2) +n lg n. (a) Check that the master method cannot be applied to this recurrence; (3 POINTS) 2 (b) Use a recursion tree to determine a good asymptotic upper bound. What is the height of the tree? What is the number of leaves of the tree? Get a bound for the inside cost and for the fringe cost. (3 POINTS) (c) Use the substitution method to solve the recurrence using the bound found in part (b). (2 POINTS)