Latest revision as of 23:23, 5 June 2026

Consider the following matrix multiplication code in C:

for(i=1; i<=x; i++) {
	for(j=1; j<=y; j++) {
		C[i][j] = 0;
		for(k=1; k<=z; k++) {
			C[i][j] += A[i][k] * B[k][j];
		}
	}
}

Each loop is proportional to O(x), O(y), and O(z), respectively, so the overall order of the computation is $O(x \cdot y \cdot z)$

If the dimensions are all equal, this is a cubic algorithm $$ O(n^3) $$ .

@@ Line 12: / Line 12: @@
 </pre>
-Each loop is proportional to O(x), O(y), and O(z), respectively, so the overall order of the computation is <math>O(xyz)</math>
+Each loop is proportional to O(x), O(y), and O(z), respectively, so the overall order of the computation is <math>O(x \cdot y \cdot z)</math>
 If the dimensions are all equal, this is a cubic algorithm <math>O(n^3)</math>.

Algorithm Analysis/Matrix Multiplication: Difference between revisions