# Matrix Multiplication $ c_{ij} = \sum_{k=1}^n a_{ik}b_{kj} $ ## Algorithms ```python for i = 1 to n for j = 1 to n for k = 1 to n C[i, j] = A[i, k] * B[k, j] ``` This algorithm runs at $\Theta(n^3)$. - Simple [[divide-and-conquer|Divide and Conquer]] - Dividing each matrices into four $n/2 \times n/2$ sub-matrices. Eight multiplications and four additions in total. - Partition methods: copying or index calculation. - This also runs at $\Theta(n^3)$, as the recursion-tree is "bushier". - [[strassen|Strassen's algorithm for matrix multiplication]].