We can finally complete the multiplication!

Recall that

The and terms don't contribute any extra multiplications, as the computer handles these using the bit shift operator before adding everything up. Therefore we needed just three multiplications, not four!

For the purpose of this exercise however, you should use the answers from previous parts to:

• multiply the first coefficient by 256,
• multiply the middle coefficient by 16,
• take the last coefficient unchanged, and
• add up the results.

How can we express in terms of , , and ?

Write an equation which expresses in terms of and .

The Strassen algorithm is a divide-and-conquer algorithm for multiplying two by matrices, where is a power of two. Similar to the Karatsuba trick, this gives a speedup on the brute force method for multiplying matrices, and its analysis follows similarly. Here, we use the Master Theorem to explicitly give a time bound on the Strassen algorithm.

Given two matrices and , we first split them each into 4 smaller square matrices, as follows.

and 

What are the dimensions of each of the matrices ?

We now look to compute our overhead function, so we can use the Master Theorem. How much work is done to divide the matrix, and how much work is done to recombine? (You may want to consider the operations used to do so).

Give your answer in the form "O(f)", where f is your function inputted with no spaces. Use the caret "^" for exponentiation, and n as the function variable. For example, if you thought the solution was , you would input O(n^42). 

Hence, find the time complexity of the Strassen algorithm. 

To input your answer, use the same form as the previous question.

For example, if I wanted to input the time complexity for the Karatsuba algorithm, I would enter O(n^{log3/log2}). Recall that .

Suppose that we did not prove that a valid flow corresponds to some valid solution. Select all the flaws that could follow.

Select the diagram that matches the recurrence. 

The red block refers to the current subproblem and the blue blocks refer to previously computed subproblems

Select the diagram that matches the recurrence. 

The red block refers to the current subproblem and the blue blocks refer to previously computed subproblems