Solve using a change of variables: .

To warm up, consider the following question. (No need to submit an 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 n 2 work), and then recurses on each of the four quadrants. This could be expressed as T(n) = 4T( n/2 ) + n 2 , meaning the parameter used for the problem size in T is the matrix dimension. Another option is to express the time complexity as T(n^2 ) = 4T( n^2/4 ) + n 2 . Here, the parameter used for the problem size is the total number of elements. In this case, because this parameter is a function of n (other than just n itself), we could set m = n 2 , define S(m) = T(n^2 ), and get S(m) = 4S( m/4 ) + m. Whats the solution in each case (in terms of n)? It should be the same

T(n) =T(vn) +1 KG = 1