title: Algorithm for matrix addition and multiplication
body: <p>Let m, n be integers such that 0&lt;= m,n&lt; N. </p>
  
  <p>Define:</p>
  
  <pre><code>  Algorithm A: Computes m + n in time O(A(N))
  
    Algorithm B: Computes m*n in time O(B(N))
  
    Algorithm C: Computes m mod n in time O(C(N))
  </code></pre>
  
  <p>Using any combination of algorithms A, B and C describe an algorithm for N X N matrix addition and matrix multiplication with entries in Z/NZ. Also indicate the algorithm's run time big-O notation. </p>
  
  <p>Attempt at solution:</p>
  
  <p>For N X N addition in Z/NZ:
  Let A, and B be N X N matrices in Z/NZ with entries a_{ij} and b_{ij} such that i,j in {0,1,...,N} where i represents the row and j represents the column in the matrix. Also, let A + B = C</p>
  
  <pre><code>Step 1. Run Algorithm A to get a_{ij} + b_{ij} = c_{ij}   in time O(A(N))
  
  Step 2. Run Algorithm C to get c_{ij} mod N in time O(C(N))
  </code></pre>
  
  <p>Repeat Steps 1 and 2  for all i,j in {0,1,...,N}.</p>
  
  <p>This means that we have to repeat the steps 1,2 N^2 times. So the total run time is estimated by</p>
  
  <pre><code> N^2[ O(A(N)) + O(C(N)) ] = O(N^2 A(N)) + O(N^2 C(N)) = O(|N^2 A(N)| + |(N^2 C(N)|).
  </code></pre>
  
  <p>For multiplication algorithm I just replaced step 1 by Algorithm B and got the total run time to be<code>O(|N^2 B(N)| + |(N^2 C(N)|)</code>  just like above.</p>
  
  <p>Please tell me if I am approaching this problem correctly, especially with the big-O notation. </p>
  
  <p>Thanks. </p>