The method of explicit substitution can help us to solve a recurrence relation. It expands out the recurrence a few times until a pattern emerges. For instance, let us start with the recurrence T (n) = 2 T (n/2) + cn. where c is a positive constant. By repeatedly applying this rule, we can bound T (n) in terms of T (n/2), then T (n/22), then T (n/23), and so on, at each step getting closer to the basis value of T (1) = O(1): T(n) = 2 T(n/2) + cn = 2[2 T(n/22) + cn/2] + cn = 22 T(n/22) + 2cn = 22[2 T(n/23) + cn/22] + 2cn = 23 T(n/23) + 3cn = ... A pattern is emerging. The general term is T(n) = 2k T(n/2k) + kcn. Plugging in k = lg n, we get T(n) = n T(1) + cnlg n = (nlg n). Do the same thing for the following recurrence T(n) = 3 T( n 2 ) + cn. (a) What is the general kth term in this case? (8 points) (b) What value of k should be plugged in to get the answer? (8 points)