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.

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. 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. 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.

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