(25 marks) A certain algorithm has running time T(n) on input of size n given by T(n) = nblg nc + 2n 2 blg nc+1 . (a) Prove that T(n) is (n log n). (b) Prove that T(n) n lg n is O(n). (c) Explain why the limit rule could not be used for (b). Hint: Let L(n) := lg n blg nc and think about the properties of the function L. For example, how large can it be, and what values does it take when n = 1, 2, . . . ?

4. (25 marks) A certain algorithm has running time T(n) on input of size n given by T (n) = n Lign+ 2n-211g n+1 (a) Prove that T (n) is (n log n). (b) Prove that T(n) -nlgn is O(n) (c) Explain why the limit rule could not be used for (b) Hint: Let L(n) := lgn-ugn] and think about the properties of the function L. For example, how large can it be, and what values does it take when n = 1, 2