For positive integers n, define T(n) using this recurrence: T(n) = {2.T( /2 for 1 n 10, 2-T([n/2] +5)+n for n > 11. Our goal is to show T(n) = O(n lg n), without using the Master Theorem. (This resembles the mergesort recurrence, except for the "+5" shifting term. In this problem we show that we get the same asymptotic upper bound.) (a) Argue that T(n) is non-decreasing. That is, T(n) s T(n+1) for all n1. Use induction. (b) Find constants c and d, so that T(2k+10) s 2k(k+c)-d for all integers k0. Use induction on k, and give explicit values for c and d. (c) Using (a) and (b), conclude that T(n) is O(n lg n).