This assignment is about the following algorithm, which multiplies two square matrices A and B to produce a new square matrix C. Each matrix has size n n. The algorithm uses a notation similar to that of the Rosen text.

1 for i := 1 to n 2 for j := 1 to n 3 c_ij := 0 4 for k := 1 to n 5 c_ij := c_ij + a_ik b_kj

1. (5 points.) Suppose that a primitive operation is either an assignment (:=), an addition (+), or a multiplication (). How many primitive operations does the algorithm perform? You must count only the primitive operations in lines 3 and 5.

2. (5 points.) Using the result of question 1, prove that the algorithm performs O(n³) primitive operations. You must find constants according to the definition of O on page 205 of Rosen.

3. (10 points.) Using the result of question 1, prove that the algorithm performs more than O(n) primitive operations. You must use the definition of O on page 205 of Rosen.

Note that questions 2 and 3 use some mathematics