Each matrix has size n n.

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           cij := 0  4           for k := 1 to n   5               cij := cij + aik × bkj

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. Prove that the algorithm performs O(n3) primitive operations. You must find constants C and k.

3. Prove that the algorithm performs more than O(n) primitive operations. You must use the definition of O.