4. (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, . . . ?