Algorithm Analysis/Matrix Multiplication: Difference between revisions

Revision as of 06:57, 29 May 2017

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(xyz) $$

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

@@ Line 21: / Line 21: @@
 {{CSFlag}}
-[[Category:Algorithms]]
+{{AlgorithmComplexityFlag}}
+[[Category:Java]]
 [[Category:C]]
-[[Category:Java]]