2. [10 marks] The master theorem cannot be applied to the following recurrence: T(n) = 2T(n/2) + n lg n. However, recurrences of the above form are not rare in algorithm design and analysis. In this question, you are asked to use the recursion-tree method to solve the above recurrence. You can assume that T(1) = 1 and that n is a power of 2 for convenience. Give your solution using big-O notation.