This problem compares the real run time of the simple (n^3 ) time algorithm and Strassens (n^2.81) time algorithm for solving the Matrix Multiplication problem. For simiplicity, we assume n = 2^j is a power of 2; and we only calculate the time needed for additions/subtractions and multiplications on matrix elements. Let T1(n) be the real run time of the simple algorithm. Let T2(n) be the real run time of Strassens algorithm.

Assume that the addition/subtraction of two numbers takes 0.25 unit time, and the multiplication of two numbers takes 1 unit time (a reasonable assumption for real machines).

For the base case n = 1, both algorithms perform one multiplication and no addition, thus take 1 unit time. The simple algorithm makes 8 recursive calls to multiply two n/2 n/2 matrices, plus 4 additions of two n/2 n/2 matrices. Thus T1(n) satisfies:

T1(1) = 1, T1(n) = 8T1(n/2) + 0.25n^2

Strassens algorithm makes 7 recursive calls to multiply two n/2 n/2 matrices, plus 18 additions/subtractions of two n/2 n/2 matrices. Thus T2(n) satisfies:

T2(1) = 1, T2(n) = 7T2(n/2) + 1.125n^2

(a) Find the exact solution of T1(n) and T2(n) when n = 2^j .

(b) Tabulate the value of T1(2^j ) and T2(2^j ) for 0 j 8.

(c) From the table, determine the break-even point of the two algorithms. (It is enough to find j such that the break-even point is between 2^j and 2^j+1).