title: Matrix multiplication worst case, best case and average case complexity
body: <p>What is the (a) worst case, (b) best case, and (c) average case complexity of the following function which does matrix multiplication</p>
  
  <pre><code>for i=1 to n do
      for j=1 to n do
          C[i,j]=0
          for k=1 to n do
              C[i,j]=C[i,j]+A[i,k]*B[k,j]
          end {for}
      end {for}
  end {for}
  </code></pre>
  
  <p>How would you justify the complexity?</p>