(d) A clever computer scientist has devised a divide-and-conquer method for multi- plying n x n matrices A and B, in case n is a power of 2. The first step is to divide A into four n/2 x n/2 submatrices, and to do likewise for B 92,2 Next, the computer scientist showed that AB can be computed using just seven multiplications of the submatrices A and Bi, as well as some additions and subtractions of n/2 x n/2 matrices. The divide-and-conquer method mentioned follows from this result. Write down a recurrence relation for the total number T (n) of real number arithmetic operations needed by this divide-and-conquer al- gorithm e) Use the master theorem to solve this recurrence: Then the computing time T(n) satisfies a recurrence which in simplified form (omitting terms of degree less than k) appears as follows T(n) aT(n/b) cn (master recurrence) The following fact can be used to solve the master recurrence FACT (Master theorem) Suppose that a function T(n) satisfies the above master recurrence, where n is a power of b. Thern T(n)(ogn, ifa-b f) Is this divide-and-conquer algorithm superior in efficiency to the standard method? Why