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.