4. Solve T(n) = T( + log n (a) with a recursion tree (b) by substitution (induction) (c) with the master method, after applying a change of variables, n-2 To warm up for (c), consider the following question which you do not need to answer Think of an abstract recursive algorithm that operates on a n n matrix: It does non-recursive work proportional to the number of elements in the matrix (say just n2 work), and then recurses on each of the four quadrants. This could be expressed as T(n)-4T(5) +, by describing the matrix side length as the parameter, or as S(n2) = 4S( ) + n2, by describing the total number of elements as the parameter. Here we could set m n2 to have S(m) 4S( ) + m. What's the solution in each case? It should be the same because we are describing the same thing. The general lesson here is that you can be creative when describing the problem size, in order to get a recurrence that's easy to deal with. 4. Solve T(n) = T( + log n (a) with a recursion tree (b) by substitution (induction) (c) with the master method, after applying a change of variables, n-2 To warm up for (c), consider the following question which you do not need to answer Think of an abstract recursive algorithm that operates on a n n matrix: It does non-recursive work proportional to the number of elements in the matrix (say just n2 work), and then recurses on each of the four quadrants. This could be expressed as T(n)-4T(5) +, by describing the matrix side length as the parameter, or as S(n2) = 4S( ) + n2, by describing the total number of elements as the parameter. Here we could set m n2 to have S(m) 4S( ) + m. What's the solution in each case? It should be the same because we are describing the same thing. The general lesson here is that you can be creative when describing the problem size, in order to get a recurrence that's easy to deal with